//
//  AlgorithmII.swift
//  LeetcodeTest
//
//  Created by Peng on 2021/11/10.
//

import UIKit

class AlgorithmII {

}

// MARK: 第 1 天 - 二分查找 (-- 2021-11-10)
extension AlgorithmII {
    
    // MARK: #34. 在排序数组中查找元素的第一个和最后一个位置
    
    /// #34. 在排序数组中查找元素的第一个和最后一个位置
    ///
    /// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    ///
    /// 如果数组中不存在目标值 target，返回 [-1, -1]。
    ///
    /// 进阶：
    ///
    ///     你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [5,7,7,8,8,10], target = 8
    ///     输出：[3,4]
    /// 示例 2：
    ///
    ///     输入：nums = [5,7,7,8,8,10], target = 6
    ///     输出：[-1,-1]
    /// 示例 3：
    ///
    ///     输入：nums = [], target = 0
    ///     输出：[-1,-1]
    ///
    /// 提示：
    ///
    ///     0 <= nums.length <= 10^5
    ///     -10^9 <= nums[i] <= 10^9
    ///     nums 是一个非递减数组
    ///     -10^9 <= target <= 10^9
    ///
    /// 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
    ///
    /// - Parameters:
    ///   - nums: 按照升序排列的整数数组 nums
    ///   - target: 目标值 target
    /// - Returns: 找出给定目标值在数组中的开始位置和结束位置
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.count < 1 || nums[0] > target || nums[nums.count - 1] < target {
            return [-1, -1]
        }
        
        var indexRange = [-1, -1]
        
//        let index = binarySearch(nums, target)
//        if index != -1 {
//            for i in 0...index {
//                if nums[index - i] != target {
//                    break
//                }
//                indexRange[0] = index - i
//            }
//
//            for i in 0...(nums.count - 1 - index) {
//                if nums[index + i] != target {
//                    break
//                }
//                indexRange[1] = index + i
//            }
//        }
        let l = binarySearchForFirstEqualOrMore(nums, target)
        let r = binarySearchForFirstEqualOrMore(nums, target+1) - 1
        if l >= 0, l < nums.count, nums[l] == target {
            indexRange[0] = l
            indexRange[1] = r
        }
        
        return indexRange
    }
    
    func binarySearchForFirstEqualOrMore(_ nums: [Int], _ target: Int, _ lft: Int = 0, _ rgt: Int = 0) -> Int {
        var l = 0, r = nums.count - 1
        if lft >= 0 { l = lft }
        if rgt > 0, rgt < r { r = rgt }
        
        if nums.count == 0 { return -1 }
        if nums[l] >= target { return l }
//        if nums[r] < target { return nums.count }
        
        var res = nums.count
        while l <= r {
            let i = (l + r) / 2
            if nums[i] < target {
                l = i + 1
            } else {
                r = i - 1
                res = i
            }
        }
        return res
    }
    
    func binarySearch(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count - 1
        if r < 0 || nums[l] > target || nums[r] < target { return -1 }
        
        while l <= r {
            let i = (l + r) / 2
            if nums[i] == target {
                return i
            }
            if nums[i] < target {
                l = i + 1
            } else {
                r = i - 1
            }
        }
        return -1
    }
    
    
    /// 二分查找
    /// - Parameters:
    ///   - nums: 升序数组
    ///   - target: 目标值
    ///   - lft: 左边界
    ///   - rgt: 右边界
    /// - Returns: 返回下标值，未存在则返回-1
    func binarySearch(_ nums: [Int], _ target: Int, _ lft: Int, _ rgt: Int) -> Int {
        var l = lft, r = rgt
        if nums.count == 0 { return -1 }
        if l < 0 || l >= nums.count || nums[l] > target { return -2 }
        if r < 0 || r >= nums.count || nums[r] < target { return -3 }
        
        while l <= r {
            let i = (l + r) / 2
            if nums[i] == target {
                return i
            }
            if nums[i] < target {
                l = i + 1
            } else {
                r = i - 1
            }
        }
        return -1
    }
    
    // MARK: #33. 搜索旋转排序数组
    
    /// #33. 搜索旋转排序数组
    ///
    /// 整数数组 nums 按升序排列，数组中的值 互不相同 。
    ///
    /// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
    ///
    /// 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [4,5,6,7,0,1,2], target = 0
    ///     输出：4
    /// 示例 2：
    ///
    ///     输入：nums = [4,5,6,7,0,1,2], target = 3
    ///     输出：-1
    /// 示例 3：
    ///
    ///     输入：nums = [1], target = 0
    ///     输出：-1
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 5000
    ///     -10^4 <= nums[i] <= 10^4
    ///     nums 中的每个值都 独一无二
    ///     题目数据保证 nums 在预先未知的某个下标上进行了旋转
    ///     -10^4 <= target <= 10^4
    ///
    /// 进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：12 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.6 MB, 在所有 Swift 提交中击败了82.14%的用户
    ///     通过测试用例：195 / 195
    ///
    /// 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
    /// - Parameters:
    ///   - nums: 旋转的排序数组。如：[4,5,6,7,0,1,2]。
    ///   - target: 目标值 target
    /// - Returns: 存在 target ，返回下标，否则，返回 -1
    func searchInRotatedSortedArray(_ nums: [Int], _ target: Int) -> Int {
        if nums.count == 0 { return -1 }
        
        var l = 0, r = nums.count - 1
        
        while l <= r {
            let m = (l + r) / 2
            if nums[m] == target {
                return m
            }
            if nums[l] <= nums[m] {
                if target >= nums[l], target < nums[m] {
                    r = m - 1
                }
                else if target < nums[m], target > nums[r] {
                    // 优化：增加 break 判断，减少执行时间（leetcode 16ms -> 12ms）。
                    break
                }
                else {
                    l = m + 1
                }
            } else {
                if target > nums[m], target <= nums[r] {
                    l = m + 1
                }
                else if target < nums[l], target > nums[m] {
                    break
                }
                else {
                    r = m - 1
                }
            }
        }
        return -1
    }
    
    // MARK: #74. 搜索二维矩阵 (-- 2021-11-11)
    
    /// #74. 搜索二维矩阵
    ///
    /// 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
    ///
    /// - 每行中的整数从左到右按升序排列。
    /// - 每行的第一个整数大于前一行的最后一个整数。
    ///
    /// 示例 1：
    ///
    ///     输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
    ///     输出：true
    /// 示例 2：
    ///
    ///     输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
    ///     输出：false
    ///
    /// 提示：
    ///
    ///     m == matrix.length
    ///     n == matrix[i].length
    ///     1 <= m, n <= 100
    ///     -10^4 <= matrix[i][j], target <= 10^4
    ///
    /// - 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：击败了67.14%的用户
    ///     内存消耗：在所有 Swift 提交中击败了84.29%的用户
    ///     通过测试用例：133 / 133
    ///
    /// - Parameters:
    ///   - matrix: 按升序排列的矩阵 matrix
    ///   - target: target
    /// - Returns: 存在 target ，返回 true， 否则，返回 false 。
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        
//        for nums in matrix {
//            if let num = nums.last, target <= num {
//                return binarySearch(nums, target) == -1 ? false : true;
//            }
//        }
        
        // 优化： 两次二分查找
        var l = 0, r = matrix.count - 1
        if r < 0 { return false }
        var row = -1
        while l <= r {
            let i = (l + r) / 2
            if matrix[i][0] <= target {
                l = i + 1
                row = i
            } else {
                r = i - 1
            }
        }
        
        if row > -1 {
            return binarySearch(matrix[row], target) == -1 ? false : true
        }
        return false
    }
    
}

//MARK: 第 2 天 - 二分查找 (-- 2021-11-11)
extension AlgorithmII {
    
    // MARK: #153. 寻找旋转排序数组中的最小值
    
    /// #153. 寻找旋转排序数组中的最小值
    ///
    /// 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] /// 在变化后可能得到：
    ///
    ///     若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
    ///     若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
    /// 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
    ///
    /// 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [3,4,5,1,2]
    ///     输出：1
    ///     解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
    /// 示例 2：
    ///
    ///     输入：nums = [4,5,6,7,0,1,2]
    ///     输出：0
    ///     解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
    /// 示例 3：
    ///
    ///     输入：nums = [11,13,15,17]
    ///     输出：11
    ///     解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
    ///
    /// 提示：
    ///
    ///     n == nums.length
    ///     1 <= n <= 5000
    ///     -5000 <= nums[i] <= 5000
    ///     nums 中的所有整数 互不相同
    ///     nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
    ///
    /// 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
    ///
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：12 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.5 MB, 在所有 Swift 提交中击败了93.62%的用户
    ///     通过测试用例：150 / 150
    ///
    /// - Parameter nums: 一个升序排序的数组，并进行了 1 至 n 次旋转。
    /// - Returns: 返回最小值
    func findMin(_ nums: [Int]) -> Int {
        if nums.count == 0 { return -1 }
        
        var lft = 0, rgt = nums.count - 1
        var minimum = nums[0]
        
        while lft <= rgt {
            if nums[lft] <= nums[rgt] {
                minimum = min(nums[lft], minimum)
                break
            }
            
            let mid = (lft + rgt) / 2
            if nums[lft] <= nums[mid] {
                minimum = min(nums[lft], minimum)
                lft = mid + 1
            } else {
                minimum = min(nums[mid], minimum)
                rgt = mid - 1
            }
        }
        return minimum
    }
    
    // MARK: #162. 寻找峰值
    
    /// #162. 寻找峰值
    ///
    /// 峰值元素是指其值严格大于左右相邻值的元素。
    ///
    /// 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
    ///
    /// 你可以假设 nums[-1] = nums[n] = -∞ 。
    ///
    /// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [1,2,3,1]
    ///     输出：2
    ///     解释：3 是峰值元素，你的函数应该返回其索引 2。
    /// 示例 2：
    ///
    /// 输入：nums = [1,2,1,3,5,6,4]
    /// 输出：1 或 5
    /// 解释：你的函数可以返回索引 1，其峰值元素为 2；
    ///      或者返回索引 5， 其峰值元素为 6。
    ///
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 1000
    ///     -2^31 <= nums[i] <= 2^31 - 1
    ///     对于所有有效的 i 都有 nums[i] != nums[i + 1]
    ///
    /// 链接：https://leetcode-cn.com/problems/find-peak-element
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：24 ms, 在所有 Swift 提交中击败了67.00%的用户
    ///     内存消耗：13.5 MB, 在所有 Swift 提交中击败了89.00%的用户
    ///     通过测试用例：63 / 63
    ///
    /// - Parameter nums: <#nums description#>
    /// - Returns: 找到并返回峰值元素索引
    func findPeakElement(_ nums: [Int]) -> Int {
        if nums.count == 0 { return -1 }
        if nums.count == 1 { return 0 }
        
        var geater = true
        for i in 1..<nums.count {
            if nums[i] > nums[i-1] {
                geater = true
                continue
            }
            if geater == true {
                return i - 1
            }
            geater = false
        }
        return nums.count - 1
        
        /*
         迭代爬坡

         思路与算法

         俗话说「人往高处走，水往低处流」。如果我们从一个位置开始，不断地向高处走，那么最终一定可以到达一个峰值位置。

         因此，我们首先在 [0,n) 的范围内随机一个初始位置 i，随后根据 nums[i−1],nums[i],nums[i+1] 三者的关系决定向哪个方向走：

         如果 nums[i−1]<nums[i]>nums[i+1]，那么位置 i 就是峰值位置，我们可以直接返回 i 作为答案；(/\)
         如果 nums[i−1]<nums[i]<nums[i+1]，那么位置 i 处于上坡，我们需要往右走，即 i←i+1；(//)
         如果 nums[i−1]>nums[i]>nums[i+1]，那么位置 i 处于下坡，我们需要往左走，即 i←i−1；(\\)
         如果 nums[i−1]>nums[i]<nums[i+1]，那么位置 i 位于山谷，两侧都是上坡，我们可以朝任意方向走。(\/)
         如果我们规定对于最后一种情况往右走，那么当位置 i 不是峰值位置时：
            如果 nums[i]<nums[i+1]，那么我们往右走；
            如果 nums[i]>nums[i+1]，那么我们往左走。
         
         */
    }
    
}

// MARK: 第 3 天 - 双指针 (-- 2021-11-15)
extension AlgorithmII {
    
    // MARK: #82. 删除排序链表中的重复元素 II
    
    /// #82. 删除排序链表中的重复元素 II
    ///
    /// 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
    ///
    /// 返回同样按升序排列的结果链表。
    ///
    /// 示例 1：
    ///
    ///     输入：head = [1,2,3,3,4,4,5]
    ///     输出：[1,2,5]
    /// 示例 2：
    ///
    ///     输入：head = [1,1,1,2,3]
    ///     输出：[2,3]
    ///
    /// 提示：
    ///
    ///     链表中节点数目在范围 [0, 300] 内
    ///     -100 <= Node.val <= 100
    ///     题目数据保证链表已经按升序排列
    ///
    /// - 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
    func deleteDuplicatesII(_ head: ListNode?) -> ListNode? {
        let node = ListNode(-1, head)
        var next1: ListNode? = node
        while (next1 != nil) {
            var count = 0
            let next2 = next1?.next
            while next2 != nil, next2?.next != nil, next2!.val == next2!.next!.val {
                next2?.next = next2?.next?.next
                count += 1
            }
            if count > 0 {
                next1?.next = next2?.next
            } else {
                next1 = next1?.next
            }            
        }
        
        return node.next
    }
    
    // MARK: 15. 三数之和
    
    /// # 15. 三数之和
    ///
    /// 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
    ///
    /// 注意：答案中不可以包含重复的三元组。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [-1,0,1,2,-1,-4]
    ///     输出：[[-1,-1,2],[-1,0,1]]
    /// 示例 2：
    ///
    ///     输入：nums = []
    ///     输出：[]
    /// 示例 3：
    ///
    ///     输入：nums = [0]
    ///     输出：[]
    ///
    /// 提示：
    ///     0 <= nums.length <= 3000
    ///     -10^5 <= nums[i] <= 10^5
    ///
    /// - 链接：https://leetcode-cn.com/problems/3sum
    ///
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 { return [] }
        let sortedNums = nums.sorted()
        let zeroFirstIndex = binarySearchForFirstEqualOrMore(sortedNums, 0)
        
        var sum: [[Int]] = []
        let length = min(zeroFirstIndex, nums.count - 3)
        var lastFirstEle = 999
        for i in 0...length {
            if lastFirstEle == sortedNums[i] {
                continue
            }
            lastFirstEle = sortedNums[i]
            let minimum = -(sortedNums[i] + sortedNums[nums.count - 1])
            let minimumIndex = binarySearchForFirstEqualOrMore(sortedNums, minimum, i+1)
            let minJ = min(max(minimumIndex, i+1), nums.count-2)
            if minJ == nums.count { continue }
            
            for j in minJ..<nums.count-1 {
                if j != i + 1, sortedNums[j] == sortedNums[j - 1] {
                    continue
                }
                
                let v = -(sortedNums[i] + sortedNums[j])
                let k = binarySearch(sortedNums, v, j+1, nums.count-1)
                if k > -1 {
                    sum.append([sortedNums[i], sortedNums[j], sortedNums[k]])
                }
                else if v <= sortedNums[j] {
                    break
                }
            }
        }
        return sum
    }
    
    static let q_15_t_315_nums = [82597,-9243,62390,83030,-97960,-26521,-61011,83390,-38677,12333,75987,46091,83794,19355,-71037,-6242,-28801,324,1202,-90885,-2989,-95597,-34333,35528,5680,89093,-90606,50360,-29393,-27012,53313,65213,99818,-82405,-41661,-3333,-51952,72135,-1523,26377,74685,96992,92263,15929,5467,-99555,-43348,-41689,-60383,-3990,32165,65265,-72973,-58372,12741,-48568,-46596,72419,-1859,34153,62937,81310,-61823,-96770,-54944,8845,-91184,24208,-29078,31495,65258,14198,85395,70506,-40908,56740,-12228,-40072,32429,93001,68445,-73927,25731,-91859,-24150,10093,-60271,-81683,-18126,51055,48189,-6468,25057,81194,-58628,74042,66158,-14452,-49851,-43667,11092,39189,-17025,-79173,13606,83172,92647,-59741,19343,-26644,-57607,82908,-20655,1637,80060,98994,39331,-31274,-61523,91225,-72953,13211,-75116,-98421,-41571,-69074,99587,39345,42151,-2460,98236,15690,-52507,-95803,-48935,-46492,-45606,-79254,-99851,52533,73486,39948,-7240,71815,-585,-96252,90990,-93815,93340,-71848,58733,-14859,-83082,-75794,-82082,-24871,-15206,91207,-56469,-93618,67131,-8682,75719,87429,-98757,-7535,-24890,-94160,85003,33928,75538,97456,-66424,-60074,-8527,-28697,-22308,2246,-70134,-82319,-10184,87081,-34949,-28645,-47352,-83966,-60418,-15293,-53067,-25921,55172,75064,95859,48049,34311,-86931,-38586,33686,-36714,96922,76713,-22165,-80585,-34503,-44516,39217,-28457,47227,-94036,43457,24626,-87359,26898,-70819,30528,-32397,-69486,84912,-1187,-98986,-32958,4280,-79129,-65604,9344,58964,50584,71128,-55480,24986,15086,-62360,-42977,-49482,-77256,-36895,-74818,20,3063,-49426,28152,-97329,6086,86035,-88743,35241,44249,19927,-10660,89404,24179,-26621,-6511,57745,-28750,96340,-97160,-97822,-49979,52307,79462,94273,-24808,77104,9255,-83057,77655,21361,55956,-9096,48599,-40490,-55107,2689,29608,20497,66834,-34678,23553,-81400,-66630,-96321,-34499,-12957,-20564,25610,-4322,-58462,20801,53700,71527,24669,-54534,57879,-3221,33636,3900,97832,-27688,-98715,5992,24520,-55401,-57613,-69926,57377,-77610,20123,52174,860,60429,-91994,-62403,-6218,-90610,-37263,-15052,62069,-96465,44254,89892,-3406,19121,-41842,-87783,-64125,-56120,73904,-22797,-58118,-4866,5356,75318,46119,21276,-19246,-9241,-97425,57333,-15802,93149,25689,-5532,95716,39209,-87672,-29470,-16324,-15331,27632,-39454,56530,-16000,29853,46475,78242,-46602,83192,-73440,-15816,50964,-36601,89758,38375,-40007,-36675,-94030,67576,46811,-64919,45595,76530,40398,35845,41791,67697,-30439,-82944,63115,33447,-36046,-50122,-34789,43003,-78947,-38763,-89210,32756,-20389,-31358,-90526,-81607,88741,86643,98422,47389,-75189,13091,95993,-15501,94260,-25584,-1483,-67261,-70753,25160,89614,-90620,-48542,83889,-12388,-9642,-37043,-67663,28794,-8801,13621,12241,55379,84290,21692,-95906,-85617,-17341,-63767,80183,-4942,-51478,30997,-13658,8838,17452,-82869,-39897,68449,31964,98158,-49489,62283,-62209,-92792,-59342,55146,-38533,20496,62667,62593,36095,-12470,5453,-50451,74716,-17902,3302,-16760,-71642,-34819,96459,-72860,21638,47342,-69897,-40180,44466,76496,84659,13848,-91600,-90887,-63742,-2156,-84981,-99280,94326,-33854,92029,-50811,98711,-36459,-75555,79110,-88164,-97397,-84217,97457,64387,30513,-53190,-83215,252,2344,-27177,-92945,-89010,82662,-11670,86069,53417,42702,97082,3695,-14530,-46334,17910,77999,28009,-12374,15498,-46941,97088,-35030,95040,92095,-59469,-24761,46491,67357,-66658,37446,-65130,-50416,99197,30925,27308,54122,-44719,12582,-99525,-38446,-69050,-22352,94757,-56062,33684,-40199,-46399,96842,-50881,-22380,-65021,40582,53623,-76034,77018,-97074,-84838,-22953,-74205,79715,-33920,-35794,-91369,73421,-82492,63680,-14915,-33295,37145,76852,-69442,60125,-74166,74308,-1900,-30195,-16267,-60781,-27760,5852,38917,25742,-3765,49097,-63541,98612,-92865,-30248,9612,-8798,53262,95781,-42278,-36529,7252,-27394,-5021,59178,80934,-48480,-75131,-54439,-19145,-48140,98457,-6601,-51616,-89730,78028,32083,-48904,16822,-81153,-8832,48720,-80728,-45133,-86647,-4259,-40453,2590,28613,50523,-4105,-27790,-74579,-17223,63721,33489,-47921,97628,-97691,-14782,-65644,18008,-93651,-71266,80990,-76732,-47104,35368,28632,59818,-86269,-89753,34557,-92230,-5933,-3487,-73557,-13174,-43981,-43630,-55171,30254,-83710,-99583,-13500,71787,5017,-25117,-78586,86941,-3251,-23867,-36315,75973,86272,-45575,77462,-98836,-10859,70168,-32971,-38739,-12761,93410,14014,-30706,-77356,-85965,-62316,63918,-59914,-64088,1591,-10957,38004,15129,-83602,-51791,34381,-89382,-26056,8942,5465,71458,-73805,-87445,-19921,-80784,69150,-34168,28301,-68955,18041,6059,82342,9947,39795,44047,-57313,48569,81936,-2863,-80932,32976,-86454,-84207,33033,32867,9104,-16580,-25727,80157,-70169,53741,86522,84651,68480,84018,61932,7332,-61322,-69663,76370,41206,12326,-34689,17016,82975,-23386,39417,72793,44774,-96259,3213,79952,29265,-61492,-49337,14162,65886,3342,-41622,-62659,-90402,-24751,88511,54739,-21383,-40161,-96610,-24944,-602,-76842,-21856,69964,43994,-15121,-85530,12718,13170,-13547,69222,62417,-75305,-81446,-38786,-52075,-23110,97681,-82800,-53178,11474,35857,94197,-58148,-23689,32506,92154,-64536,-73930,-77138,97446,-83459,70963,22452,68472,-3728,-25059,-49405,95129,-6167,12808,99918,30113,-12641,-26665,86362,-33505,50661,26714,33701,89012,-91540,40517,-12716,-57185,-87230,29914,-59560,13200,-72723,58272,23913,-45586,-96593,-26265,-2141,31087,81399,92511,-34049,20577,2803,26003,8940,42117,40887,-82715,38269,40969,-50022,72088,21291,-67280,-16523,90535,18669,94342,-39568,-88080,-99486,-20716,23108,-28037,63342,36863,-29420,-44016,75135,73415,16059,-4899,86893,43136,-7041,33483,-67612,25327,40830,6184,61805,4247,81119,-22854,-26104,-63466,63093,-63685,60369,51023,51644,-16350,74438,-83514,99083,10079,-58451,-79621,48471,67131,-86940,99093,11855,-22272,-67683,-44371,9541,18123,37766,-70922,80385,-57513,-76021,-47890,36154,72935,84387,-92681,-88303,-7810,59902,-90,-64704,-28396,-66403,8860,13343,33882,85680,7228,28160,-14003,54369,-58893,92606,-63492,-10101,64714,58486,29948,-44679,-22763,10151,-56695,4031,-18242,-36232,86168,-14263,9883,47124,47271,92761,-24958,-73263,-79661,-69147,-18874,29546,-92588,-85771,26451,-86650,-43306,-59094,-47492,-34821,-91763,-47670,33537,22843,67417,-759,92159,63075,94065,-26988,55276,65903,30414,-67129,-99508,-83092,-91493,-50426,14349,-83216,-76090,32742,-5306,-93310,-60750,-60620,-45484,-21108,-58341,-28048,-52803,69735,78906,81649,32565,-86804,-83202,-65688,-1760,89707,93322,-72750,84134,71900,-37720,19450,-78018,22001,-23604,26276,-21498,65892,-72117,-89834,-23867,55817,-77963,42518,93123,-83916,63260,-2243,-97108,85442,-36775,17984,-58810,99664,-19082,93075,-69329,87061,79713,16296,70996,13483,-74582,49900,-27669,-40562,1209,-20572,34660,83193,75579,7344,64925,88361,60969,3114,44611,-27445,53049,-16085,-92851,-53306,13859,-33532,86622,-75666,-18159,-98256,51875,-42251,-27977,-18080,23772,38160,41779,9147,94175,99905,-85755,62535,-88412,-52038,-68171,93255,-44684,-11242,-104,31796,62346,-54931,-55790,-70032,46221,56541,-91947,90592,93503,4071,20646,4856,-63598,15396,-50708,32138,-85164,38528,-89959,53852,57915,-42421,-88916,-75072,67030,-29066,49542,-71591,61708,-53985,-43051,28483,46991,-83216,80991,-46254,-48716,39356,-8270,-47763,-34410,874,-1186,-7049,28846,11276,21960,-13304,-11433,-4913,55754,79616,70423,-27523,64803,49277,14906,-97401,-92390,91075,70736,21971,-3303,55333,-93996,76538,54603,-75899,98801,46887,35041,48302,-52318,55439,24574,14079,-24889,83440,14961,34312,-89260,-22293,-81271,-2586,-71059,-10640,-93095,-5453,-70041,66543,74012,-11662,-52477,-37597,-70919,92971,-17452,-67306,-80418,7225,-89296,24296,86547,37154,-10696,74436,-63959,58860,33590,-88925,-97814,-83664,85484,-8385,-50879,57729,-74728,-87852,-15524,-91120,22062,28134,80917,32026,49707,-54252,-44319,-35139,13777,44660,85274,25043,58781,-89035,-76274,6364,-63625,72855,43242,-35033,12820,-27460,77372,-47578,-61162,-70758,-1343,-4159,64935,56024,-2151,43770,19758,-30186,-86040,24666,-62332,-67542,73180,-25821,-27826,-45504,-36858,-12041,20017,-24066,-56625,-52097,-47239,-90694,8959,7712,-14258,-5860,55349,61808,-4423,-93703,64681,-98641,-25222,46999,-83831,-54714,19997,-68477,66073,51801,-66491,52061,-52866,79907,-39736,-68331,68937,91464,98892,910,93501,31295,-85873,27036,-57340,50412,21,-2445,29471,71317,82093,-94823,-54458,-97410,39560,-7628,66452,39701,54029,37906,46773,58296,60370,-61090,85501,-86874,71443,-72702,-72047,14848,34102,77975,-66294,-36576,31349,52493,-70833,-80287,94435,39745,-98291,84524,-18942,10236,93448,50846,94023,-6939,47999,14740,30165,81048,84935,-19177,-13594,32289,62628,-90612,-542,-66627,64255,71199,-83841,-82943,-73885,8623,-67214,-9474,-35249,62254,-14087,-90969,21515,-83303,94377,-91619,19956,-98810,96727,-91939,29119,-85473,-82153,-69008,44850,74299,-76459,-86464,8315,-49912,-28665,59052,-69708,76024,-92738,50098,18683,-91438,18096,-19335,35659,91826,15779,-73070,67873,-12458,-71440,-46721,54856,97212,-81875,35805,36952,68498,81627,-34231,81712,27100,-9741,-82612,18766,-36392,2759,41728,69743,26825,48355,-17790,17165,56558,3295,-24375,55669,-16109,24079,73414,48990,-11931,-78214,90745,19878,35673,-15317,-89086,94675,-92513,88410,-93248,-19475,-74041,-19165,32329,-26266,-46828,-18747,45328,8990,-78219,-25874,-74801,-44956,-54577,-29756,-99822,-35731,-18348,-68915,-83518,-53451,95471,-2954,-13706,-8763,-21642,-37210,16814,-60070,-42743,27697,-36333,-42362,11576,85742,-82536,68767,-56103,-63012,71396,-78464,-68101,-15917,-11113,-3596,77626,-60191,-30585,-73584,6214,-84303,18403,23618,-15619,-89755,-59515,-59103,-74308,-63725,-29364,-52376,-96130,70894,-12609,50845,-2314,42264,-70825,64481,55752,4460,-68603,-88701,4713,-50441,-51333,-77907,97412,-66616,-49430,60489,-85262,-97621,-18980,44727,-69321,-57730,66287,-92566,-64427,-14270,11515,-92612,-87645,61557,24197,-81923,-39831,-10301,-23640,-76219,-68025,92761,-76493,68554,-77734,-95620,-11753,-51700,98234,-68544,-61838,29467,46603,-18221,-35441,74537,40327,-58293,75755,-57301,-7532,-94163,18179,-14388,-22258,-46417,-48285,18242,-77551,82620,250,-20060,-79568,-77259,82052,-98897,-75464,48773,-79040,-11293,45941,-67876,-69204,-46477,-46107,792,60546,-34573,-12879,-94562,20356,-48004,-62429,96242,40594,2099,99494,25724,-39394,-2388,-18563,-56510,-83570,-29214,3015,74454,74197,76678,-46597,60630,-76093,37578,-82045,-24077,62082,-87787,-74936,58687,12200,-98952,70155,-77370,21710,-84625,-60556,-84128,925,65474,-15741,-94619,88377,89334,44749,22002,-45750,-93081,-14600,-83447,46691,85040,-66447,-80085,56308,44310,24979,-29694,57991,4675,-71273,-44508,13615,-54710,23552,-78253,-34637,50497,68706,81543,-88408,-21405,6001,-33834,-21570,-46692,-25344,20310,71258,-97680,11721,59977,59247,-48949,98955,-50276,-80844,-27935,-76102,55858,-33492,40680,66691,-33188,8284,64893,-7528,6019,-85523,8434,-64366,-56663,26862,30008,-7611,-12179,-70076,21426,-11261,-36864,-61937,-59677,929,-21052,3848,-20888,-16065,98995,-32293,-86121,-54564,77831,68602,74977,31658,40699,29755,98424,80358,-69337,26339,13213,-46016,-18331,64713,-46883,-58451,-70024,-92393,-4088,70628,-51185,71164,-75791,-1636,-29102,-16929,-87650,-84589,-24229,-42137,-15653,94825,13042,88499,-47100,-90358,-7180,29754,-65727,-42659,-85560,-9037,-52459,20997,-47425,17318,21122,20472,-23037,65216,-63625,-7877,-91907,24100,-72516,22903,-85247,-8938,73878,54953,87480,-31466,-99524,35369,-78376,89984,-15982,94045,-7269,23319,-80456,-37653,-76756,2909,81936,54958,-12393,60560,-84664,-82413,66941,-26573,-97532,64460,18593,-85789,-38820,-92575,-43663,-89435,83272,-50585,13616,-71541,-53156,727,-27644,16538,34049,57745,34348,35009,16634,-18791,23271,-63844,95817,21781,16590,59669,15966,-6864,48050,-36143,97427,-59390,96931,78939,-1958,50777,43338,-51149,39235,-27054,-43492,67457,-83616,37179,10390,85818,2391,73635,87579,-49127,-81264,-79023,-81590,53554,-74972,-83940,-13726,-39095,29174,78072,76104,47778,25797,-29515,-6493,-92793,22481,-36197,-65560,42342,15750,97556,99634,-56048,-35688,13501,63969,-74291,50911,39225,93702,-3490,-59461,-30105,-46761,-80113,92906,-68487,50742,36152,-90240,-83631,24597,-50566,-15477,18470,77038,40223,-80364,-98676,70957,-63647,99537,13041,31679,86631,37633,-16866,13686,-71565,21652,-46053,-80578,-61382,68487,-6417,4656,20811,67013,-30868,-11219,46,74944,14627,56965,42275,-52480,52162,-84883,-52579,-90331,92792,42184,-73422,-58440,65308,-25069,5475,-57996,59557,-17561,2826,-56939,14996,-94855,-53707,99159,43645,-67719,-1331,21412,41704,31612,32622,1919,-69333,-69828,22422,-78842,57896,-17363,27979,-76897,35008,46482,-75289,65799,20057,7170,41326,-76069,90840,-81253,-50749,3649,-42315,45238,-33924,62101,96906,58884,-7617,-28689,-66578,62458,50876,-57553,6739,41014,-64040,-34916,37940,13048,-97478,-11318,-89440,-31933,-40357,-59737,-76718,-14104,-31774,28001,4103,41702,-25120,-31654,63085,-3642,84870,-83896,-76422,-61520,12900,88678,85547,33132,-88627,52820,63915,-27472,78867,-51439,33005,-23447,-3271,-39308,39726,-74260,-31874,-36893,93656,910,-98362,60450,-88048,99308,13947,83996,-90415,-35117,70858,-55332,-31721,97528,82982,-86218,6822,25227,36946,97077,-4257,-41526,56795,89870,75860,-70802,21779,14184,-16511,-89156,-31422,71470,69600,-78498,74079,-19410,40311,28501,26397,-67574,-32518,68510,38615,19355,-6088,-97159,-29255,-92523,3023,-42536,-88681,64255,41206,44119,52208,39522,-52108,91276,-70514,83436,63289,-79741,9623,99559,12642,85950,83735,-21156,-67208,98088,-7341,-27763,-30048,-44099,-14866,-45504,-91704,19369,13700,10481,-49344,-85686,33994,19672,36028,60842,66564,-24919,33950,-93616,-47430,-35391,-28279,56806,74690,39284,-96683,-7642,-75232,37657,-14531,-86870,-9274,-26173,98640,88652,64257,46457,37814,-19370,9337,-22556,-41525,39105,-28719,51611,-93252,98044,-90996,21710,-47605,-64259,-32727,53611,-31918,-3555,33316,-66472,21274,-37731,-2919,15016,48779,-88868,1897,41728,46344,-89667,37848,68092,-44011,85354,-43776,38739,-31423,-66330,65167,-22016,59405,34328,-60042,87660,-67698,-59174,-1408,-46809,-43485,-88807,-60489,13974,22319,55836,-62995,-37375,-4185,32687,-36551,-75237,58280,26942,-73756,71756,78775,-40573,14367,-71622,-77338,24112,23414,-7679,-51721,87492,85066,-21612,57045,10673,-96836,52461,-62218,-9310,65862,-22748,89906,-96987,-98698,26956,-43428,46141,47456,28095,55952,67323,-36455,-60202,-43302,-82932,42020,77036,10142,60406,70331,63836,58850,-66752,52109,21395,-10238,-98647,-41962,27778,69060,98535,-28680,-52263,-56679,66103,-42426,27203,80021,10153,58678,36398,63112,34911,20515,62082,-15659,-40785,27054,43767,-20289,65838,-6954,-60228,-72226,52236,-35464,25209,-15462,-79617,-41668,-84083,62404,-69062,18913,46545,20757,13805,24717,-18461,-47009,-25779,68834,64824,34473,39576,31570,14861,-15114,-41233,95509,68232,67846,84902,-83060,17642,-18422,73688,77671,-26930,64484,-99637,73875,6428,21034,-73471,19664,-68031,15922,-27028,48137,54955,-82793,-41144,-10218,-24921,-28299,-2288,68518,-54452,15686,-41814,66165,-72207,-61986,80020,50544,-99500,16244,78998,40989,14525,-56061,-24692,-94790,21111,37296,-90794,72100,70550,-31757,17708,-74290,61910,78039,-78629,-25033,73172,-91953,10052,64502,99585,-1741,90324,-73723,68942,28149,30218,24422,16659,10710,-62594,94249,96588,46192,34251,73500,-65995,-81168,41412,-98724,-63710,-54696,-52407,19746,45869,27821,-94866,-76705,-13417,-61995,-71560,43450,67384,-8838,-80293,-28937,23330,-89694,-40586,46918,80429,-5475,78013,25309,-34162,37236,-77577,86744,26281,-29033,-91813,35347,13033,-13631,-24459,3325,-71078,-75359,81311,19700,47678,-74680,-84113,45192,35502,37675,19553,76522,-51098,-18211,89717,4508,-82946,27749,85995,89912,-53678,-64727,-14778,32075,-63412,-40524,86440,-2707,-36821,63850,-30883,67294,-99468,-23708,34932,34386,98899,29239,-23385,5897,54882,98660,49098,70275,17718,88533,52161,63340,50061,-89457,19491,-99156,24873,-17008,64610,-55543,50495,17056,-10400,-56678,-29073,-42960,-76418,98562,-88104,-96255,10159,-90724,54011,12052,45871,-90933,-69420,67039,37202,78051,-52197,-40278,-58425,65414,-23394,-1415,6912,-53447,7352,17307,-78147,63727,98905,55412,-57658,-32884,-44878,22755,39730,3638,35111,39777,74193,38736,-11829,-61188,-92757,55946,-71232,-63032,-83947,39147,-96684,-99233,25131,-32197,24406,-55428,-61941,25874,-69453,64483,-19644,-68441,12783,87338,-48676,66451,-447,-61590,50932,-11270,29035,65698,-63544,10029,80499,-9461,86368,91365,-81810,-71914,-52056,-13782,44240,-30093,-2437,24007,67581,-17365,-69164,-8420,-69289,-29370,48010,90439,13141,69243,50668,39328,61731,78266,-81313,17921,-38196,55261,9948,-24970,75712,-72106,28696,7461,31621,61047,51476,56512,11839,-96916,-82739,28924,-99927,58449,37280,69357,11219,-32119,-62050,-48745,-83486,-52376,42668,82659,68882,38773,46269,-96005,97630,25009,-2951,-67811,99801,81587,-79793,-18547,-83086,69512,33127,-92145,-88497,47703,59527,1909,88785,-88882,69188,-46131,-5589,-15086,36255,-53238,-33009,82664,53901,35939,-42946,-25571,33298,69291,53199,74746,-40127,-39050,91033,51717,-98048,87240,36172,65453,-94425,-63694,-30027,59004,88660,3649,-20267,-52565,-67321,34037,4320,91515,-56753,60115,27134,68617,-61395,-26503,-98929,-8849,-63318,10709,-16151,61905,-95785,5262,23670,-25277,90206,-19391,45735,37208,-31992,-92450,18516,-90452,-58870,-58602,93383,14333,17994,82411,-54126,-32576,35440,-60526,-78764,-25069,-9022,-394,92186,-38057,55328,-61569,67780,77169,19546,-92664,-94948,44484,-13439,83529,27518,-48333,72998,38342,-90553,-98578,-76906,81515,-16464,78439,92529,35225,-39968,-10130,-7845,-32245,-74955,-74996,67731,-13897,-82493,33407,93619,59560,-24404,-57553,19486,-45341,34098,-24978,-33612,79058,71847,76713,-95422,6421,-96075,-59130,-28976,-16922,-62203,69970,68331,21874,40551,89650,51908,58181,66480,-68177,34323,-3046,-49656,-59758,43564,-10960,-30796,15473,-20216,46085,-85355,41515,-30669,-87498,57711,56067,63199,-83805,62042,91213,-14606,4394,-562,74913,10406,96810,-61595,32564,31640,-9732,42058,98052,-7908,-72330,1558,-80301,34878,32900,3939,-8824,88316,20937,21566,-3218,-66080,-31620,86859,54289,90476,-42889,-15016,-18838,75456,30159,-67101,42328,-92703,85850,-5475,23470,-80806,68206,17764,88235,46421,-41578,74005,-81142,80545,20868,-1560,64017,83784,68863,-97516,-13016,-72223,79630,-55692,82255,88467,28007,-34686,-69049,-41677,88535,-8217,68060,-51280,28971,49088,49235,26905,-81117,-44888,40623,74337,-24662,97476,79542,-72082,-35093,98175,-61761,-68169,59697,-62542,-72965,59883,-64026,-37656,-92392,-12113,-73495,98258,68379,-21545,64607,-70957,-92254,-97460,-63436,-8853,-19357,-51965,-76582,12687,-49712,45413,-60043,33496,31539,-57347,41837,67280,-68813,52088,-13155,-86430,-15239,-45030,96041,18749,-23992,46048,35243,-79450,85425,-58524,88781,-39454,53073,-48864,-82289,39086,82540,-11555,25014,-5431,-39585,-89526,2705,31953,-81611,36985,-56022,68684,-27101,11422,64655,-26965,-63081,-13840,-91003,-78147,-8966,41488,1988,99021,-61575,-47060,65260,-23844,-21781,-91865,-19607,44808,2890,63692,-88663,-58272,15970,-65195,-45416,-48444,-78226,-65332,-24568,42833,-1806,-71595,80002,-52250,30952,48452,-90106,31015,-22073,62339,63318,78391,28699,77900,-4026,-76870,-45943,33665,9174,-84360,-22684,-16832,-67949,-38077,-38987,-32847,51443,-53580,-13505,9344,-92337,26585,70458,-52764,-67471,-68411,-1119,-2072,-93476,67981,40887,-89304,-12235,41488,1454,5355,-34855,-72080,24514,-58305,3340,34331,8731,77451,-64983,-57876,82874,62481,-32754,-39902,22451,-79095,-23904,78409,-7418,77916]
}

// MARK: 第 4 天 - 双指针 （-- 2021-11-16）
extension AlgorithmII {
    
    //MARK: #844. 比较含退格的字符串
    
    /// #844. 比较含退格的字符串
    ///
    /// 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
    ///
    /// 如果相等，返回 true ；否则，返回 false 。
    ///
    /// 注意：如果对空文本输入退格字符，文本继续为空。
    ///
    /// 示例 1：
    ///
    ///     输入：s = "ab#c", t = "ad#c"
    ///     输出：true
    ///     解释：S 和 T 都会变成 “ac”。
    /// 示例 2：
    ///
    ///     输入：s = "ab##", t = "c#d#"
    ///     输出：true
    ///     解释：s 和 t 都会变成 “”。
    /// 示例 3：
    ///
    ///     输入：s = "a##c", t = "#a#c"
    ///     输出：true
    ///     解释：s 和 t 都会变成 “c”。
    /// 示例 4：
    ///
    ///     输入：s = "a#c", t = "b"
    ///     输出：false
    ///     解释：s 会变成 “c”，但 t 仍然是 “b”。
    ///
    /// 提示：
    ///
    ///     1 <= s.length, t.length <= 200
    ///     s 和 t 只含有小写字母以及字符 '#'
    ///
    /// 进阶：
    ///
    ///     你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
    ///
    /// - 链接：https://leetcode-cn.com/problems/backspace-string-compare
    /// - Parameters:
    ///   - s: s 只含有小写字母以及字符 '#'
    ///   - t: t 只含有小写字母以及字符 '#'
    /// - Returns: 如果相等，返回 true ；否则，返回 false
    func backspaceCompare(_ s: String, _ t: String) -> Bool {
        /* Way 1
         执行用时：4 ms, 在所有 Swift 提交中击败了76.00%的用户
         内存消耗：13.5 MB, 在所有 Swift 提交中击败了84.00%的用户
         通过测试用例：113 / 113
         */
//        var ss = ""
//        for c in s {
//            if c == "#" {
//                if ss.count == 0 { continue }
//                ss.removeLast()
//            } else {
//                ss.append(c)
//            }
//        }
//        
//        var tt = ""
//        for c in t {
//            if c == "#" {
//                if tt.count == 0 { continue }
//                tt.removeLast()
//            } else {
//                tt.append(c)
//            }
//        }
//        
//        return ss == tt
        
        // Way 2
        let backspace = Character("#"), nullspace = Character("\0")
        var backCount1 = 0, backCount2 = 0
        var index1 = s.endIndex
        var index2 = t.endIndex
        var c1 = nullspace, c2 = nullspace
        
        while index1 >= s.startIndex, index2 >= t.startIndex {
            if c1 == nullspace, index1 > s.startIndex {
                index1 = s.index(before: index1)
                c1 = s[index1]
            }
            
            if c2 == nullspace, index2 > t.startIndex {
                index2 = t.index(before: index2)
                c2 = t[index2]
            }
            
            if backCount1 == 0, backCount2 == 0,
                c1 != backspace, c2 != backspace {
                
                if c1 != c2 {
                    return false
                }
                
                if index1 == s.startIndex, index2 == t.startIndex {
                    break
                }
                
                c1 = nullspace
                c2 = nullspace
                continue
            }
            
            if c1 == "#" {
                backCount1 += 1
                c1 = nullspace
            }
            else if backCount1 > 0 {
                backCount1 -= 1
                c1 = nullspace
            }
            
            if c2 == "#" {
                backCount2 += 1
                c2 = nullspace
            } else if backCount2 > 0 {
                backCount2 -= 1
                c2 = nullspace
            }
        }
        
        return true
    }
    
    // MARK: #986. 区间列表的交集
    
    /// #986. 区间列表的交集
    ///
    /// 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
    ///
    /// 返回这 两个区间列表的交集 。
    ///
    /// 形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
    ///
    /// 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
    ///
    /// 示例 1：
    ///
    ///     输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
    ///     输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
    /// 示例 2：
    ///
    ///     输入：firstList = [[1,3],[5,9]], secondList = []
    ///     输出：[]
    /// 示例 3：
    ///
    ///     输入：firstList = [], secondList = [[4,8],[10,12]]
    ///     输出：[]
    /// 示例 4：
    ///
    ///     输入：firstList = [[1,7]], secondList = [[3,10]]
    ///     输出：[[3,7]]
    ///
    /// 提示：
    ///
    ///     0 <= firstList.length, secondList.length <= 1000
    ///     firstList.length + secondList.length >= 1
    ///     0 <= starti < endi <= 10^9
    ///     endi < starti+1
    ///     0 <= startj < endj <= 10^9
    ///     endj < startj+1
    ///
    /// - 链接：https://leetcode-cn.com/problems/interval-list-intersections
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：192 ms, 在所有 Swift 提交中击败了95.24%的用户
    ///     内存消耗：14.1 MB, 在所有 Swift 提交中击败了71.43%的用户
    ///     通过测试用例：85 / 85
    ///
    /// - Parameters:
    ///   - firstList: 由一些 闭区间 组成的列表
    ///   - secondList: 由一些 闭区间 组成的列表
    /// - Returns: 返回这 两个区间列表的交集 。
    func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
        let firstCount = firstList.count, secondCount = secondList.count
        
        var list: [[Int]] = []
        var i = 0, j = 0
        while i < firstCount, j < secondCount {
            let section1 = firstList[i]
            let section2 = secondList[j]
            
            let s = [max(section1[0], section2[0]), min(section1[1], section2[1])]
            if s[0] <= s[1] {
                list.append(s)
            }
            if s[1] == section1[1] {
                i += 1
            } else {
                j += 1
            }
        }
        
        return list
    }
    
    // MARK: #11. 盛最多水的容器
    
    /// #11. 盛最多水的容器
    ///
    /// 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    ///
    /// 说明：你不能倾斜容器。
    ///
    /// 示例 1：
    ///
    ///     输入：[1,8,6,2,5,4,8,3,7]
    ///     输出：49
    ///     解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
    /// 示例 2：
    ///
    ///     输入：height = [1,1]
    ///     输出：1
    /// 示例 3：
    ///
    ///     输入：height = [4,3,2,1,4]
    ///     输出：16
    /// 示例 4：
    ///
    ///     输入：height = [1,2,1]
    ///     输出：2
    ///
    /// 提示：
    ///
    ///     n == height.length
    ///     2 <= n <= 10^5
    ///     0 <= height[i] <= 10^4
    ///
    /// - 链接：https://leetcode-cn.com/problems/container-with-most-water
    /// - Parameter height: <#height description#>
    /// - Returns: <#description#>
    func maxArea(_ height: [Int]) -> Int {
        if height.count < 2 { return 0 }
        var lft = 0, rgt = height.count - 1
        
        var res = 0
        while lft < rgt {
            let h1 = height[lft], h2 = height[rgt]
            let area = min(h1, h2) * abs(lft - rgt)
            res = max(res, area)
            
            if h1 < h2 {
                lft += 1
            } else {
                rgt -= 1
            }
        }
        return res
    }
}

// MARK: 第 5 天 - 滑动窗口 （-- 2021-11-16）
extension AlgorithmII {
    
    // MARK: 438. 找到字符串中所有字母异位词
    
    /// #438. 找到字符串中所有字母异位词
    ///
    /// 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    ///
    /// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
    ///
    /// 示例 1:
    ///
    ///     输入: s = "cbaebabacd", p = "abc"
    ///     输出: [0,6]
    ///     解释:
    ///     起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
    ///     起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
    ///  示例 2:
    ///
    ///     输入: s = "abab", p = "ab"
    ///     输出: [0,1,2]
    ///     解释:
    ///     起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
    ///     起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
    ///     起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
    ///
    /// 提示:
    ///
    ///     1 <= s.length, p.length <= 3 * 10^4
    ///     s 和 p 仅包含小写字母
    ///
    /// - 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
    ///
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        if s.count < p.count { return [] }
        
        var counter = Array(repeating: 0, count: 26)
        let aAsciiValue = Int("a".first!.asciiValue!)
        for c in p {
            let v = Int(c.asciiValue!) - aAsciiValue
            counter[v] += 1
        }
        
        var indexs: [Int] = []
        var counter1 = counter
        var ss = ""
        var start = 0
        for (i, ch) in s.enumerated() {
            let v = Int(ch.asciiValue!) - aAsciiValue
            if counter[v] == 0 {
                if start > 0 {
                    counter1 = counter
                }
                start = 0
                ss = ""
                continue
            }
            if counter1[v] == 0 {
                let upper =  ss.firstIndex(of: ch)!
                for chch in ss[ss.startIndex...upper] {
                    let vv = Int(chch.asciiValue!) - aAsciiValue
                    counter1[vv] += 1
                    start -= 1
                }
                ss.removeSubrange(ss.startIndex...upper)
            }
            
            counter1[v] -= 1
            start += 1
            ss.append(ch)
            if counter1.max() == 0 {
                indexs.append(i - p.count + 1)
            }
            
        }
        
        return indexs
    }
    
    // MARK: #713. 乘积小于K的子数组
    
    
    /// #713. 乘积小于K的子数组
    ///
    /// 给定一个正整数数组 nums和整数 k 。
    ///
    /// 请找出该数组内乘积小于 k 的连续的子数组的个数。
    ///
    /// 示例 1:
    ///
    ///      输入: nums = [10,5,2,6], k = 100
    ///      输出: 8
    ///      解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
    ///      需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
    /// 示例 2:
    ///
    ///     输入: nums = [1,2,3], k = 0
    ///     输出: 0
    ///
    /// 提示:
    ///
    ///     1 <= nums.length <= 3 * 10^4
    ///     1 <= nums[i] <= 1000
    ///     0 <= k <= 10^6
    ///
    /// - 链接：https://leetcode-cn.com/problems/subarray-product-less-than-k
    ///
    /// - Parameters:
    ///   - nums: 正整数数组
    ///   - k: 整数
    /// - Returns: 该数组内乘积小于 k 的连续的子数组的个数
    func numSubarrayProductLessThanK(_ nums: [Int], _ k: Int) -> Int {
        var n = 0
        // 1
        for i in 0..<nums.count {
            var pro = 1
            for j in i..<nums.count {
                pro *= nums[i]
                if pro >= k {
                    break
                }
                n += 1
            }
        }
        
        // 2
        var nums1 = Array<Int>()
        for num in nums {
            if num >= k {
                nums1 = []
                continue
            }
            
            nums1.append(1)
            for i in (0..<nums1.count).reversed() {
                let v = nums1[i] * num
                if v >= k {
                    nums1.removeFirst(i+1)
                    break
                } else {
                    nums1[i] = v
                    n += 1
                }
            }
        }
        
        // 滑动窗口
        
        return n
    }
    
    // MARK: 209. 长度最小的子数组
    
    /// #209. 长度最小的子数组
    ///
    /// 给定一个含有 n 个正整数的数组和一个正整数 target 。
    ///
    /// 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
    ///
    /// 示例 1：
    ///
    ///     输入：target = 7, nums = [2,3,1,2,4,3]
    ///     输出：2
    ///     解释：子数组 [4,3] 是该条件下的长度最小的子数组。
    /// 示例 2：
    ///
    ///     输入：target = 4, nums = [1,4,4]
    ///     输出：1
    /// 示例 3：
    ///
    ///     输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    ///     输出：0
    ///
    /// 提示：
    ///
    ///     1 <= target <= 10^9
    ///     1 <= nums.length <= 10^5
    ///     1 <= nums[i] <= 10^5
    ///
    /// 进阶：
    ///
    ///     如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：48 ms, 在所有 Swift 提交中击败了89.36%的用户
    ///     内存消耗：14 MB, 在所有 Swift 提交中击败了96.81%的用户通过测试用例：19 / 19
    ///     通过测试用例：19 / 19
    ///
    /// - 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        if nums.count == 0 { return 0 }
        if target == 0 { return 1 }
        
        var sum = 0
        var lft = 0
        var minLen = nums.count + 1
        
        for (idx, num) in nums.enumerated() {
            sum += num
            
            if sum < target {
                continue
            }
            
            var len = idx - lft + 1
            while (sum - nums[lft] >= target) {
                sum -= nums[lft]
                lft += 1
                len -= 1
            }
            
            minLen = min(minLen, len)
            
            if minLen == 1 { break }
        }
        
        return minLen <= nums.count ? minLen : 0;
    }
}

// MARK: 第 6 天 - 广度优先搜索 / 深度优先搜索 (-- 2021-11-17)
extension AlgorithmII {
    
    // MARK: #200. 岛屿数量
    
    /// #200. 岛屿数量
    ///
    /// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
    ///
    /// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
    ///
    /// 此外，你可以假设该网格的四条边均被水包围。
    ///
    /// 示例 1：
    ///
    ///     输入：grid = [
    ///       ["1","1","1","1","0"],
    ///       ["1","1","0","1","0"],
    ///       ["1","1","0","0","0"],
    ///       ["0","0","0","0","0"]
    ///     ]
    ///     输出：1
    /// 示例 2：

    ///     输入：grid = [
    ///       ["1","1","0","0","0"],
    ///       ["1","1","0","0","0"],
    ///       ["0","0","1","0","0"],
    ///       ["0","0","0","1","1"]
    ///     ]
    ///     输出：3
    ///
    /// 提示：
    ///
    ///     m == grid.length
    ///     n == grid[i].length
    ///     1 <= m, n <= 300
    ///     grid[i][j] 的值为 '0' 或 '1'
    ///
    /// - 链接：https://leetcode-cn.com/problems/number-of-islands
    ///
    /// - Parameter grid: 由 '1'（陆地）和 '0'（水）组成的的二维网格
    /// - Returns: 网格中岛屿的数量
    func numIslands(_ grid: [[Character]]) -> Int {
        
        func dfs(_ mat: inout [[Character]], _ target: Character, _ position: (Int, Int), _ replace: Bool = false, _ new: Character = Character("0")) -> Int {
            
            let row = mat.count, col = row > 0 ? mat[0].count : 0;
            let i = position.0, j = position.1
            
            if i < 0 || i > row - 1 || j < 0 || j > col - 1 { return 0 }
            if mat[i][j] != target { return 0 }
            
            mat[i][j] = new

            var area = 1
            
            // up, down, left, right
            let diretions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
            for diretion in diretions {
                area += dfs(&mat, target, (i + diretion[0], j + diretion[1]), replace, new)
            }
            
            return area
        }
        
        let row = grid.count, col = row > 0 ? grid[0].count : 0;
        var m = grid
        var count = 0
        
        for i in 0..<row {
            for j in 0..<col {
                if m[i][j] == "0" {
                    continue
                }
                let _ = dfs(&m, Character("1"), (i, j), true, Character("0"))
                count += 1
            }
        }
        return count
    }
    
    // MARK: #547. 省份数量
    
    /// #547. 省份数量
    ///
    /// 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c /// 间接相连。
    ///
    /// 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
    ///
    /// 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 /// isConnected[i][j] = 0 表示二者不直接相连。
    ///
    /// 返回矩阵中 省份 的数量。
    ///
    /// 示例 1：
    ///
    ///     输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
    ///     输出：2
    /// 示例 2：
    ///
    ///     输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
    ///     输出：3
    ///
    /// 提示：
    ///
    ///     1 <= n <= 200
    ///     n == isConnected.length
    ///     n == isConnected[i].length
    ///     isConnected[i][j] 为 1 或 0
    ///     isConnected[i][i] == 1
    ///     isConnected[i][j] == isConnected[j][i]
    ///
    /// - 链接：https://leetcode-cn.com/problems/number-of-provinces
    ///
    /// - Parameter isConnected:  n x n 的矩阵
    /// - Returns: description
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        var p = n
        
        var flags = Array(repeating: Array(repeating: 0, count: n), count: n)
        
        func dfs(_ x: Int, y: Int) {
            
            if x < 0 || x >= n { return }
            if y < 0 || y >= n { return }
            
            if flags[x][y] == 0 {
                flags[x][y] = 1
                flags[y][x] = 1
                
                let connected = isConnected[x][y]
                
                if connected == 1 {
                    if x != y, (flags[x][x] == 0 || flags[y][y] == 0) {
                        flags[x][x] = 1
                        flags[y][y] = 1
                        
                        p -= 1
                        dfs(0, y: x)
                    }
                }
            }
            
            dfs(x + 1, y: y)
        }
        
        for i in 0..<n {
            if flags[i][i] == 1 {
                continue
            }
            dfs(i, y: i)
        }
        return n
    }
}

// MARK: 第 7 天 - 广度优先搜索 / 深度优先搜索 (-- 2021-11-18)
extension AlgorithmII {
    
    // MARK: #117. 填充每个节点的下一个右侧节点指针 II
    
    /**
     * Definition for a Node.
     */
     public class Node {
         public var val: Int
         public var left: Node?
         public var right: Node?
         public var next: Node?
         public init(_ val: Int) {
             self.val = val
             self.left = nil
             self.right = nil
             self.next = nil
         }
     }
    
    /// 117. 填充每个节点的下一个右侧节点指针 II
    ///
    /// 给定一个二叉树
    /// 
    ///     struct Node {
    ///       int val;
    ///       Node *left;
    ///       Node *right;
    ///       Node *next;
    ///     }
    /// 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
    ///
    /// 初始状态下，所有 next 指针都被设置为 NULL。
    ///
    /// 进阶：
    ///
    ///     你只能使用常量级额外空间。
    ///     使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
    ///
    /// 示例：
    ///
    ///     Tree 1                     Tree 2
    ///           1                          1 -> null
    ///         /   \                      /   \
    ///        2     3                    2  ->  3 -> null
    ///       / \   / \                 /   \      \
    ///      4   5 6   7               4 ->  5   -> 7 -> null
    ///
    ///     输入：root = [1,2,3,4,5,null,7]
    ///     输出：[1,#,2,3,#,4,5,7,#]
    ///     解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B /// 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
    ///
    /// 提示：
    ///
    ///     树中的节点数小于 6000
    ///     -100 <= node.val <= 100
    ///
    /// - 链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：36 ms, 在所有 Swift 提交中击败了97.14%的用户
    ///     内存消耗：14.1 MB, 在所有 Swift 提交中击败了97.14%的用户
    ///     通过测试用例 55/55
    ///
    func connect(_ root: Node?) -> Node? {
        if root == nil { return nil }
        
        func dfs(_ cur: Node?, next: Node?) {
            if cur == nil { return }
            
            /* error on ___
                                 1
                        2                3
                      4       5       _     6
                    7   _   _   _         _   8

            */
            
//            cur?.next = next
            
//            dfs(cur?.left, next: cur?.right ?? (next?.left ?? next?.right)) // 22/55. [1,2,3,4,null,null,5]
//            dfs(cur?.right, next: next?.left ?? (next?.right ?? next?.next?.left ?? next?.next?.right))
            
            var node = cur
            var last: Node?
            var nextFloor: Node?
            while node != nil {
                if let l = node?.left {
                    if last != nil { last?.next = l}
                    last = l
                    
                    if nextFloor == nil { nextFloor = l }
                }
                if let r = node?.right {
                    if last != nil { last?.next = r}
                    last = r
                    
                    if nextFloor == nil { nextFloor = r }
                }
                node = node?.next
            }
            
            dfs(nextFloor, next: nil)
        }
        
        func bfs(_ nodes: [Node]) {
            if nodes.count == 0 { return }
            var lastNode: Node?
            var nextNodes: [Node] = []
            
            for node in nodes {
                if lastNode != nil {
                    lastNode?.next = node
                }
                if let l = node.left {
                    nextNodes.append(l)
                }
                if let r = node.left {
                    nextNodes.append(r)
                }
                lastNode = node
            }
            
            bfs(nextNodes)
        }
        
        bfs([root!])
        return root
    }
    
    // MARK: #572. 另一棵树的子树
    
    /**
     * Definition for a binary tree node.
     */
    public class TreeNode {
        public var val: Int
        public var left: TreeNode?
        public var right: TreeNode?
        public init() { self.val = 0; self.left = nil; self.right = nil; }
        public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
        public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
            self.val = val
            self.left = left
            self.right = right
        }
    }
    
    /// #572. 另一棵树的子树
    ///
    /// 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
    ///
    /// 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
    ///
    /// 示例 1：
    ///
    ///     root 1                     subRoot 2
    ///           3                          4
    ///         /   \                      /   \
    ///        4     5                    1     2
    ///       / \
    ///      1   2
    ///
    ///     输入：root = [3,4,5,1,2], subRoot = [4,1,2]
    ///     输出：true
    /// 示例 2：
    ///
    ///     root 1                     subRoot 2
    ///           3                          4
    ///         /   \                      /   \
    ///        4     5                    1     2
    ///       / \
    ///      1   2
    ///         /
    ///        0
    ///
    ///     输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
    ///     输出：false
    ///
    /// 提示：
    ///
    ///     root 树上的节点数量范围是 [1, 2000]
    ///     subRoot 树上的节点数量范围是 [1, 1000]
    ///     -10^4 <= root.val <= 10^4
    ///     -10^4 <= subRoot.val <= 10^4
    ///
    /// - 链接：https://leetcode-cn.com/problems/subtree-of-another-tree
    ///
    func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
        // 暴力法 时间复杂度 O(r * s) 超时限
        
        func same(_ node1: TreeNode?, _ node2: TreeNode?) -> Bool {
            if node1 == nil, node2 == nil { return true }
            
            if node1 == nil || node2 == nil { return false }
            if node1!.val != node2!.val { return false }
            
            if same(node1?.left, node2?.left), same(node1?.right, node2?.right) {
                return true
            }
            return false
        }
        
        func dfs(_ node1: TreeNode?, _ node2: TreeNode?) -> Bool {
            
            if same(node1, node2) {
                return true
            }
            
            if node1!.val == subRoot!.val, node1!.val != node2?.val {
//                return dfs(node1, subRoot)
            }
            
            return dfs(node1?.left, subRoot) || dfs(node1?.right, subRoot)
        }
        
        return dfs(root, subRoot)
    }
}


// MARK: 第 8 天 - 广度优先搜索 / 深度优先搜索 (-- 2021-11-19)
extension AlgorithmII {
    
    // MARK: #1091. 二进制矩阵中的最短路径
    
    /// #1091. 二进制矩阵中的最短路径
    ///
    /// 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
    ///
    /// 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
    ///
    ///     路径途经的所有单元格都的值都是 0 。
    ///     路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
    ///     畅通路径的长度 是该路径途经的单元格总数。
    ///
    /// 示例 1：
    ///
    ///     输入：grid = [[0,1],[1,0]]
    ///     输出：2
    /// 示例 2：
    ///
    ///     输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
    ///     输出：4
    /// 示例 3：
    ///
    ///     输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
    ///     输出：-1
    ///
    /// 提示：
    ///
    ///     n == grid.length
    ///     n == grid[i].length
    ///     1 <= n <= 100
    ///     grid[i][j] 为 0 或 1
    ///
    /// - 链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        
        // 深度返回值还有问题！
        func dfs(_ mat: [[Int]], _ visited: inout [[Int]], _ x: Int, y: Int) -> Int {
            let raw = mat.count, col = mat.first?.count ?? 0
            
            if x < 0 || x >= raw || y < 0 || y >= col { return 0 }
            
            if visited[x][y] != -1 { return visited[x][y] }
            
            // 此路不通
            visited[x][y] = 0
            if mat[x][y] == 1 {
                return 0
            }
            
            if x == raw - 1, y == col - 1 {
                visited[x][y] = 1
                return 1
            }
            
            /* 上下左右+四角共8个方位，按优先级排列。
                  5   4   2
                    ↖︎ ↑ ↗︎
                  4 ← 0 → 3
                    ↙︎ ↓ ↘︎
                  2   3   1
             */
            let dirs = [[1, 1],
                        
                        [1, 0], [0, 1],
                        [1, -1], [-1, 1],
                        [0, -1], [-1, 0],
                        [-1, -1]]
            let max = (raw + col) * 2
            var minimum = max
            for dir in dirs {
                let step = dfs(mat, &visited, x + dir[0], y: y + dir[1])
                if step > 0 {
                    minimum = min(minimum, step)
                }
            }
            visited[x][y] = minimum == max ? 0: minimum + 1
            return visited[x][y]
        }
        
        var visited = Array(repeating: Array(repeating: -1, count: grid[0].count), count: grid.count)
        
//        let mini = dfs(grid, &visited, 0, y: 0)
//        if mini < 1 { return -1 }
        
        let pos = [[0, 0]]
        let v = q_1091_bfs(grid, &visited, pos, 1)
        let r = visited.last!.last!
        return r > 0 ? r : -1;
    }
    
    func q_1091_bfs(_ mat: [[Int]], _ visited: inout [[Int]], _ positions: [[Int]], _ round: Int) -> Int {
        if positions.count == 0 { return 0 }
        
        let dirs = [[1, 1],
                    [1, 0], [0, 1],
                    [1, -1], [-1, 1],
                    [0, -1], [-1, 0],
                    [-1, -1]]
        
        var news: [[Int]] = []
        
        for idx in 0..<positions.count {
            let position = positions[idx]
            
            if mat[position[0]][position[1]] == 1 {
                    return 0
            }
            
            visited[position[0]][position[1]] = round
            
            for dir in dirs {
                let p = [position[0] + dir[0], position[1] + dir[1]]
                if p[0] < 0 || p[0] >= visited.count ||
                    p[1] < 0 || p[1] >= visited.count {
                    continue
                }
                if visited[p[0]][p[1]] != -1 {
                    continue
                }
                visited[p[0]][p[1]] = 0
                
                if mat[p[0]][p[1]] == 1 {
                    continue
                }
                
                news.append(p)
            }
        }
        
        if news.count == 0 { return 1}
        
        let v = q_1091_bfs(mat, &visited, news, round + 1)
        return v > 0 ? v + 1: 0;
    }
    
    // MARK: #130. 被围绕的区域
    
    /// #130. 被围绕的区域
    /// 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
    ///
    /// 示例 1：
    ///
    ///          ["X","X","X","X"],                 ["X","X","X","X"],
    ///          ["X","O","O","X"],                 ["X","X","X","X"],
    ///          ["X","X","O","X"],       =>        ["X","X","X","X"],
    ///          ["X","O","X","X"]]                 ["X","O","X","X"]]
    ///
    ///     输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
    ///     输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
    ///     解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。  任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
    /// 示例 2：
    ///
    ///     输入：board = [["X"]]
    ///     输出：[["X"]]
    ///
    /// 提示：
    ///
    ///     m == board.length
    ///     n == board[i].length
    ///     1 <= m, n <= 200
    ///     board[i][j] 为 'X' 或 'O'
    ///
    /// - 链接：https://leetcode-cn.com/problems/surrounded-regions
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：112 ms, 在所有 Swift 提交中击败了94.44%的用户
    ///     内存消耗：15 MB, 在所有 Swift 提交中击败了83.33%的用户
    ///     通过测试用例：58 / 58
    ///
    func solve(_ board: inout [[Character]]) {
        let raw = board.count, col = board.first?.count ?? 0
        
        var visited = Array(repeating: Array(repeating: -1, count: col), count: raw)
        
        for i in 0..<raw {
            q_130_dfs(&board, &visited, SIMDInt2(i, 0))
            q_130_dfs(&board, &visited, SIMDInt2(i, col - 1))
        }
        for i in 2..<col - 1 {
            q_130_dfs(&board, &visited, SIMDInt2(0, i))
            q_130_dfs(&board, &visited, SIMDInt2(raw - 1, i))
        }
        
        let chX = Character("X")
        for i in 0..<raw {
            for j in 0..<col {
                if visited[i][j] == 1 || board[i][j] == chX {
                    continue
                }
                board[i][j] = chX
            }
        }
    }
    
    public typealias SIMDInt2 = SIMD2<Int>

    func q_130_dfs(_ mat: inout [[Character]], _ visited: inout [[Int]], _ pos: SIMDInt2) {
        
        let raw = mat.count, col = mat.first?.count ?? 0
        let chO = Character("O")
        
        if visited[pos.x][pos.y] != -1 { return }
        
        visited[pos.x][pos.y] = 1
        
        if mat[pos.x][pos.y] != chO { return }
        
        let dirs = [SIMDInt2(-1, 0), SIMDInt2(1, 0), SIMDInt2(0, -1), SIMDInt2(0, 1)]
        for dir in dirs {
            let newpos = pos &+ dir
            
            if newpos.x < 0 || newpos.x >= raw || newpos.y < 0 || newpos.y >= col {
                continue
            }
            if visited[newpos.x][newpos.y] != -1 {
                continue
            }
            
            q_130_dfs(&mat, &visited, newpos)
        }
    }
    
    // MARK: #797. 所有可能的路径
    
    /// #797. 所有可能的路径
    ///
    /// 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
    ///
    /// 二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
    ///
    /// 译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
    ///
    /// 示例 1：
    ///
    ///     输入：graph = [[1,2],[3],[3],[]]
    ///     输出：[[0,1,3],[0,2,3]]
    ///     解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
    /// 示例 2：
    ///
    ///     输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
    ///     输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
    /// 示例 3：
    ///
    ///     输入：graph = [[1],[]]
    ///     输出：[[0,1]]
    /// 示例 4：
    ///
    ///     输入：graph = [[1,2,3],[2],[3],[]]
    ///     输出：[[0,1,2,3],[0,2,3],[0,3]]
    /// 示例 5：
    ///
    ///     输入：graph = [[1,3],[2],[3],[]]
    ///     输出：[[0,1,2,3],[0,3]]
    ///
    /// 提示：
    ///
    ///     n == graph.length
    ///     2 <= n <= 15
    ///     0 <= graph[i][j] < n
    ///     graph[i][j] != i（即，不存在自环）
    ///     graph[i] 中的所有元素 互不相同
    ///     保证输入为 有向无环图（DAG）
    ///
    /// - 链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：72 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：15.2 MB, 在所有 Swift 提交中击败了97.14%的用户
    /// 	通过测试用例：30 / 30
    /// - Parameter graph: graph
    /// - Returns: paths
    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        
        var paths: [[Int]] = []
        var path: [Int] = []
        
        func dfs(_ startIndex: Int) {
            if startIndex >= graph.count { return }
            
            if startIndex == graph.count - 1 {
                paths.append(path)
                return
            }
            
            for idx in graph[startIndex] {
                path.append(idx)
                dfs(idx)
                path.removeLast()
            }
        }
        path.append(0)
        dfs(0)
        
        return paths
    }
}


// #MARK: 第 9 天 - 递归 / 回溯 (-- 2021-11-21)
extension AlgorithmII {
    
    // MARK: #78. 子集
    
    /// #78. 子集
    ///
    /// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    ///
    /// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [1,2,3]
    ///     输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    /// 示例 2：
    ///
    ///     输入：nums = [0]
    ///     输出：[[],[0]]
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 10
    ///     -10 <= nums[i] <= 10
    ///     nums 中的所有元素 互不相同
    ///
    /// - 链接：https://leetcode-cn.com/problems/subsets
    func subsets(_ nums: [Int]) -> [[Int]] {
        
        var subsets: [[Int]] = []
        
        func bfs(_ startIndex: Int) {
            if startIndex >= nums.count {
                return
            }
            
            for i in 0..<subsets.count {
                var subset = subsets[i]
                subset.append(nums[startIndex])
                subsets.append(subset)
            }
            
            bfs(startIndex+1)
        }
        
        subsets.append([])
        bfs(0)
        
        return subsets
    }
    
    // MARK: #90. 子集 II
    
    /// #90. 子集 II
    ///
    /// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
    ///
    /// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [1,2,2]
    ///     输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
    /// 示例 2：
    ///
    ///     输入：nums = [0]
    ///     输出：[[],[0]]
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 10
    ///     -10 <= nums[i] <= 10
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：4 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.7 MB, 在所有 Swift 提交中击败了93.75%的用户
    ///     通过测试用例：20 / 20
    ///
    /// 链接：https://leetcode-cn.com/problems/subsets-ii
    /// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
        var subsets: [[Int]] = []
        
//        var dups: [Int: Int] = [:]
//
//        func bfs(_ startIndex: Int) {
//            if startIndex >= nums.count {
//                return
//            }
//
//            var idx = 0
//            if let c = dups[nums[startIndex]], c > 0 {
//                idx = subsets.count - 1
//            }
//            dups[nums[startIndex]] = 1
//
//            for i in idx..<subsets.count {
//                var subset = subsets[i]
//                subset.append(nums[startIndex])
//                subsets.append(subset)
//            }
//
//            bfs(startIndex+1)
//        }
//
//        subsets.append([])
//        bfs(0)
        
        /* DFS
         */
        var subpath: [Int] = []
        
        func dfs(_ startIndex: Int) {
            guard startIndex < nums.count else {
                return
            }
            
            if subpath.count == 0, startIndex > 0, nums[startIndex] == nums[startIndex - 1] {
                dfs(startIndex+1)
                return
            }
            
            subpath.append(nums[startIndex])
            subsets.append(subpath)
            
            var idx = startIndex + 1
            while idx < nums.count {
                if idx == startIndex + 1 || nums[idx] != nums[idx - 1] {
                    dfs(idx)
                }
                idx += 1
            }
            
            subpath.removeLast()
            
            if subpath.count == 0 {
                dfs(startIndex+1)
            }
        }
        
        subsets.append(subpath)
        dfs(0)
        
        return subsets
    }
}

// #MARK: 第 10 天 - 递归 / 回溯 (-- 2021-11-22)
extension AlgorithmII {
    
    // MARK: #47. 全排列 II
    
    ///
    /// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
    ///
    ///
    ///示例 1：
    ///
    ///     输入：nums = [1,1,2]
    ///     输出：
    ///     [[1,1,2],
     ///     [1,2,1],
     ///     [2,1,1]]
    /// 示例 2：
    ///
    ///     输入：nums = [1,2,3]
    ///     输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    ///
    /// 提示：
    ///     1 <= nums.length <= 8
    ///     -10 <= nums[i] <= 10
    ///
    /// - 链接：https://leetcode-cn.com/problems/permutations-ii
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：20 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.7 MB, 在所有 Swift 提交中击败了92.63%的用户
    ///     通过测试用例：33 / 33
    ///
    /// - Parameter nums: 包含重复数字的序列 nums
    /// - Returns: 所有不重复的全排列
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        let nums = nums.sorted()
        
        var permutes: [[Int]] = []
        var permute: [Int] = []
        var temp: [Int] = nums
        
        func dfs() {
            if permute.count == nums.count {
                permutes.append(permute)
                return
            }
            
            var last: Int?
            for _ in 0..<temp.count {
                let num = temp.removeFirst()
                
                if let last = last, last != num {
                    permute.append(num)
                    dfs()
                    permute.removeLast()
                }
                last = num
                
                temp.append(num)
            }
        }
        
        dfs()
        return permutes
    }
    
    // MARK: #39. 组合总和
    
    /// #39. 组合总和
    ///
    /// 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
    ///
    /// candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
    ///
    /// 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
    ///
    /// 示例 1：
    ///
    ///     输入: candidates = [2,3,6,7], target = 7
    ///     输出: [[7],[2,2,3]]
    /// 示例 2：
    ///
    ///     输入: candidates = [2,3,5], target = 8
    ///     输出: [[2,2,2,2],[2,3,3],[3,5]]
    /// 示例 3：
    ///
    ///     输入: candidates = [2], target = 1
    ///     输出: []
    /// 示例 4：
    ///
    ///     输入: candidates = [1], target = 1
    ///     输出: [[1]]
    /// 示例 5：
    ///
    ///     输入: candidates = [1], target = 2
    ///     输出: [[1,1]]
    ///
    /// 提示：
    ///
    ///     1 <= candidates.length <= 30
    ///     1 <= candidates[i] <= 200
    ///     candidate 中的每个元素都是独一无二的。
    ///     1 <= target <= 500
    ///
    /// - 链接：https://leetcode-cn.com/problems/combination-sum
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：12 ms, 在所有 Swift 提交中击败了96.20%的用户
    ///     内存消耗：13.5 MB, 在所有 Swift 提交中击败了88.61%的用户
    ///     通过测试用例：170 / 170
    ///
    /// - Parameters:
    ///   - candidates: 无重复元素的正整数数组 candidates
    ///   - target:  正整数 target
    /// - Returns: 所有可以使数字和为目标数 target 的唯一组合
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let candidates = candidates.sorted()
        
        var combinations: [[Int]] = []
        var combination: [Int] = []
        var sum = 0
        
        func dfs(_ start: Int) {
            if sum > target { return }
            if sum == target {
                combinations.append(combination)
                return
            }
            
            for i in start..<candidates.count {
                let num = candidates[i]

                if sum + num > target {
                    break
                }

                sum += num
                combination.append(num)
                                
                dfs(i)

                combination.removeLast()
                sum -= num
            }
        }
        
        dfs(0)
        return combinations
    }
    
    // MARK: #40. 组合总和 II
    
    /// #40. 组合总和 II
    ///
    /// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    ///
    /// candidates 中的每个数字在每个组合中只能使用一次。
    ///
    /// 注意：解集不能包含重复的组合。
    ///
    /// 示例 1:
    ///
    ///     输入: candidates = [10,1,2,7,6,1,5], target = 8,
    ///     输出:
    ///     [
    ///     [1,1,6],
    ///     [1,2,5],
    ///     [1,7],
    ///     [2,6]
    ///     ]
    /// 示例 2:
    ///
    ///     输入: candidates = [2,5,2,1,2], target = 5,
    ///     输出:
    ///     [
    ///     [1,2,2],
    ///     [5]
    ///     ]
    ///
    /// 提示:
    ///
    ///     1 <= candidates.length <= 100
    ///     1 <= candidates[i] <= 50
    ///     1 <= target <= 30
    ///
    /// - 链接：https://leetcode-cn.com/problems/combination-sum-ii
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：8 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.5 MB, 在所有 Swift 提交中击败了87.50%的用户
    ///     通过测试用例：175 / 175
    ///
    /// - Parameters:
    ///   - candidates: 数组
    ///   - target: 目标数 target
    /// - Returns: 所有可以使数字和为 target 的组合
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let candidates = candidates.sorted()
        
        var combinations: [[Int]] = []
        var combination: [Int] = []
        var sum = 0
        
        func dfs(_ start: Int) {
            if sum > target { return }
            if sum == target {
                combinations.append(combination)
                return
            }
            
            var last: Int?
            for i in start..<candidates.count {
                let num = candidates[i]

                if sum + num > target {
                    break
                }
                if let last = last, last == num {
                    continue
                }
                last = num
                
                sum += num
                combination.append(num)
                                
                dfs(i+1)

                combination.removeLast()
                sum -= num
            }
        }
        
        dfs(0)
        return combinations
    }
}

// MARK: 第 11 天 - 递归 / 回溯 (-- 2021-11-23)
extension AlgorithmII {
    
    // MARK: #17. 电话号码的字母组合
    
    /// #17. 电话号码的字母组合
    ///
    /// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
    ///
    /// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    ///
    /// 示例 1：

    ///     输入：digits = "23"
    ///     输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
    /// 示例 2：
    ///
    ///     输入：digits = ""
    ///     输出：[]
    /// 示例 3：
    ///
    ///     输入：digits = "2"
    ///     输出：["a","b","c"]
    ///
    /// 提示：
    ///
    ///     0 <= digits.length <= 4
    ///     digits[i] 是范围 ['2', '9'] 的一个数字。
    ///
    /// - 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
    ///
    /// 执行用时：0 ms, 在所有 Swift 提交中击败了100.00%的用户
    /// 内存消耗：13.6 MB, 在所有 Swift 提交中击败了88.81%的用户
    /// 通过测试用例：25 / 25
    ///
    /// - Parameter digits:包含数字 2-9 的字符串
    /// - Returns:
    func letterCombinations(_ digits: String) -> [String] {
        let letters = "abcdefghijklmnopqrstuvwxyz"
        let counts = [0, 0, 3, 3, 3,
                      3, 3, 4, 3, 4]
        
        var startIndex = letters.startIndex
        let digitMaps = counts.map { count -> [Character] in
            var ltrs: [Character] = []
            for _ in 0..<count {
                if startIndex == letters.endIndex { break }
                
                ltrs.append(letters[startIndex])
                startIndex = letters.index(after: startIndex)
            }
            return ltrs
        }
        
        var combinations: [String] = []
        var combination: String = ""
        
        func dfs(_ digits: String, _ index: String.Index, _ digitMaps: [[Character]]) {
            if index == digits.endIndex {
                combinations.append(combination)
                return
            }
            let digit = digits[index]
            let value = Int("\(digit)")!
            
            for ch in digitMaps[value] {
                combination.append(ch)
                
                dfs(digits, digits.index(after: index), digitMaps)
                
                combination.removeLast()
            }
        }
        
        dfs(digits, digits.startIndex, digitMaps)
        return combinations
    }
    
    // MARK: #22. 括号生成
    
    // MARK: #79. 单词搜索
    
    /// #79. 单词搜索
    ///
    /// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
    ///
    /// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    ///
    /// 示例 1：
    ///
    ///     ["A","B","C","E"],   ["A","B","C"," "],
    ///     ["S","F","C","S"],   [" "," ","C"," "],
    ///     ["A","D","E","E"],   [" "," ","E"," "]
    ///     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    ///     输出：true
    /// 示例 2：
    ///
    ///     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
    ///     输出：true
    /// 示例 3：
    ///
    ///     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
    ///     输出：false
    ///
    /// 提示：
    ///
    ///     m == board.length
    ///     n = board[i].length
    ///     1 <= m, n <= 6
    ///     1 <= word.length <= 15
    ///     board 和 word 仅由大小写英文字母组成
    ///
    /// - 链接：https://leetcode-cn.com/problems/word-search
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：512 ms, 在所有 Swift 提交中击败了70.77%的用户
    ///     内存消耗：13.8 MB, 在所有 Swift 提交中击败了58.46%的用户
    ///     通过测试用例：80 / 80
    ///
    /// - Parameters:
    ///   - board:  m x n 二维字符网格 board。仅由大小写英文字母组成
    ///   - word: 字符串单词 word
    /// - Returns: 如果 word 存在于网格中，返回 true ；否则，返回 false 。
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        let row = board.count, col = board.first?.count ?? 0
        var visited = Array(repeating: Array(repeating: -1, count: col), count: row)
        
        func dfs(_ board: [[Character]], _ idx: String.Index, _ x: Int, _ y: Int) -> Bool {
            if visited[x][y] != -1 {
                return false
            }
            if  board[x][y] != word[idx] {
                return false
            }
            
            visited[x][y] = 1
            
            if idx == word.index(before: word.endIndex) {
                return true
            }
            
            let dirs = [SIMDInt2(-1, 0), SIMDInt2(1, 0), SIMDInt2(0, -1), SIMDInt2(0, 1)]
            let nextIdx = word.index(after: idx)
            for dir in dirs {
                let x1 = x + dir.x, y1 = y + dir.y
                if  x1 >= 0, x1 < row, y1 >= 0, y1 < col,
                dfs(board, nextIdx, x1, y1) {
                    return true
                }
            }
            
            visited[x][y] = -1
            return false
        }
        
        for i in 0..<row {
            for j in 0..<col {
                if board[i][j] == word.first!, dfs(board, word.startIndex, i, j) {
                    return true
                }
            }
        }
        
        return false
    }
}

// MARK: 第 12 天 - 动态规划
extension AlgorithmII {
    
    // MARK: #213. 打家劫舍 II
    
    // MARK: #55. 跳跃游戏
}

// MARK: 第 13 天 - 动态规划
extension AlgorithmII {
    
    // MARK: #45. 跳跃游戏 II
    ///
    /// 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
    ///
    /// 数组中的每个元素代表你在该位置可以跳跃的最大长度。
    ///
    /// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    ///
    /// 假设你总是可以到达数组的最后一个位置。
    ///
    /// 示例 1:
    ///
    ///     输入: nums = [2,3,1,1,4]
    ///     输出: 2
    ///     解释: 跳到最后一个位置的最小跳跃数是 2。
    ///      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
    /// 示例 2:
    ///
    ///     输入: nums = [2,3,0,1,4]
    ///     输出: 2
    ///
    /// 提示:
    ///
    ///     1 <= nums.length <= 104
    ///     0 <= nums[i] <= 1000
    ///
    /// - 链接：https://leetcode-cn.com/problems/jump-game-ii
    ///
    func jump2(_ nums: [Int]) -> Int {
        
        var minimums = Array(repeating: -1, count: nums.count)
        let maximum = nums.count - 1
        var minimum = maximum
        var count = 0
        
        /* 递归 O(n^2)
         执行用时：132 ms, 在所有 Swift 提交中击败了21.50%的用户
         内存消耗：15.7 MB, 在所有 Swift 提交中击败了5.61%的用户
         通过测试用例：106 / 106
         */
        func dfs(_ idx: Int) {
            
            if idx >= maximum   {
                minimums[idx] = 0
                minimum = min(minimum, count)
                return
            }
            
            if idx + nums[idx] >= nums.count - 1 {
                minimums[idx] = 1
                minimum = min(minimum, count+1)
                return
            }
            
            if count >= minimum {
                return
            }
            
            count += 1
            
            var num = nums[idx]
            var next = maximum - idx
            
            while num > 0 {
                if minimums[idx + num] == -1 {
                    dfs(idx + num)
                }
                if minimums[idx + num] != -1 {
                    next = min(next, minimums[idx + num])
                    
                    if (minimums[idx + num] < 2) {break}
                }
                
                num -= 1
            }
            
            if next != maximum - idx {
                minimum = min(minimum, count + next)
                minimums[idx] = next + 1
            }
            
            count -= 1
            
        }
        
        dfs(0)
        return minimum
    }
    
    // MARK: #62. 不同路径
    
    /// #62. 不同路径
    ///
    /// 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    ///
    /// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    ///
    /// 问总共有多少条不同的路径？
    ///
    /// 示例 1：
    ///
    ///     输入：m = 3, n = 7
    ///     输出：28
    /// 示例 2：
    ///
    ///     输入：m = 3, n = 2
    ///     输出：3
    ///     解释：
    ///     从左上角开始，总共有 3 条路径可以到达右下角。
    ///     1. 向右 -> 向下 -> 向下
    ///     2. 向下 -> 向下 -> 向右
    ///     3. 向下 -> 向右 -> 向下
    /// 示例 3：
    ///
    ///     输入：m = 7, n = 3
    ///     输出：28
    /// 示例 4：
    ///
    ///     输入：m = 3, n = 3
    ///     输出：6
    ///
    /// 提示：
    ///
    ///     1 <= m, n <= 100
    ///     题目数据保证答案小于等于 2 * 109
    ///
    /// - 链接：https://leetcode-cn.com/problems/unique-paths
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：0 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.3 MB, 在所有 Swift 提交中击败了85.29%的用户
    ///     通过测试用例：62 / 62
    ///
    /// - Parameters:
    ///   - m: raw
    ///   - n: col
    /// - Returns: <#description#>
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var mat = Array(repeating:Array(repeating: 1, count: n), count:m)
        for i in 1..<m {
            for j in 1..<n {
                mat[i][j] = mat[i-1][j] + mat[i][j-1]
            }
        }
        return mat.last!.last!
    }
}

// MARK: 第 14 天 - 动态规划 (-- 2021-11-23)
extension AlgorithmII {
    
    // MARK: #5. 最长回文子串
    
    /// #5. 最长回文子串
    ///
    /// 给你一个字符串 s，找到 s 中最长的回文子串。
    ///
    /// 示例 1：
    ///
    ///     输入：s = "babad"
    ///     输出："bab"
    ///     解释："aba" 同样是符合题意的答案。
    /// 示例 2：
    ///
    ///     输入：s = "cbbd"
    ///     输出："bb"
    /// 示例 3：
    ///
    ///     输入：s = "a"
    ///     输出："a"
    /// 示例 4：
    ///
    ///     输入：s = "ac"
    ///     输出："a"
    ///
    /// 提示：
    ///
    /// 1 <= s.length <= 1000
    /// s 仅由数字和英文字母（大写和/或小写）组成
    ///
    /// - 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
    ///
    /// - Parameter s: <#s description#>
    /// - Returns: <#description#>
    func longestPalindrome(_ s: String) -> String {
        // test119 超时
        
        /// 中心扩散
        func checkPalindrome(_ str: String, _ lowwer: String.Index, _ upper: String.Index) -> (String.Index, String.Index)? {
            if upper == str.endIndex || str[lowwer] != str[upper] {
                return nil
            }

            if lowwer > str.startIndex,
            let range = checkPalindrome(str, str.index(before: lowwer), str.index(after: upper))  {
                return range
            }

            return (lowwer, upper)
        }
        
        var startIndex = s.startIndex
        let endIndex = s.endIndex
        
        var maxLen = 0
        var maxS = ""
        var count = s.count
        var i = 0
        
        while startIndex < endIndex {
            let next = s.index(after: startIndex)
            
            if count - i < maxLen / 2 {
                break
            }
            
            if let r = checkPalindrome(s, startIndex, next) {
                let d = s.distance(from: r.0, to: r.1) + 1
                if d > maxLen {
                    maxLen = d
                    maxS = String(s[r.0...r.1])
                }
            }
            if let r = checkPalindrome(s, startIndex, startIndex) {
                let d = s.distance(from: r.0, to: r.1) + 1
                if d > maxLen {
                    maxLen = d
                    maxS = String(s[r.0...r.1])
                }
            }
            startIndex = next
            i += 1
        }
        
        return maxS
    }
    
    // MARK: #413. 等差数列划分
    
    /// #413. 等差数列划分
    ///
    /// 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
    ///
    ///     例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
    /// 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
    ///
    /// 子数组 是数组中的一个连续序列。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [1,2,3,4]
    ///     输出：3
    ///     解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
    /// 示例 2：
    ///
    ///     输入：nums = [1]
    ///     输出：0
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 5000
    ///     -1000 <= nums[i] <= 1000
    ///
    /// - 链接：https://leetcode-cn.com/problems/arithmetic-slices
    ///
    /// 执行结果：通过
    ///     执行用时：4 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：14.5 MB, 在所有 Swift 提交中击败了8.33%的用户
    ///     通过测试用例：15 / 15
    ///
    /// - Parameter nums: <#nums description#>
    /// - Returns: <#description#>
    func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
        if nums.count < 3 { return 0 }
        
        func numberOfSubslices(_ count: Int) -> Int {
            if count < 3 { return 0 }
            var n = 0
            for i in 3..<count+1 {
                n += count - i + 1
            }
            return n
        }
        
        var n = 0
        
        var distance = 0
        var count = 0
        
        func dfs(_ idx: Int) {
            if idx >= nums.count {
                n += numberOfSubslices(count)
                return
            }

            if count >= 2 {
                if distance != nums[idx] - nums[idx-1] {
                    n += numberOfSubslices(count)
                    count = 1
                }
            }
            
            count += 1
            
            if count == 2 {
                distance = nums[idx] - nums[idx - 1]
            }
            
            dfs(idx + 1)
        }
        
        dfs(0)
        return n
    }
}

// MARK: 第 15 天 - 动态规划 (-- 2021-11-25)
extension AlgorithmII {
    // MARK: #91. 解码方法
    
    /// #91. 解码方法
    ///
    /// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
    ///
    ///     'A' -> 1
    ///     'B' -> 2
    ///     ...
    ///     'Z' -> 26
    /// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
    ///
    ///     "AAJF" ，将消息分组为 (1 1 10 6)
    ///     "KJF" ，将消息分组为 (11 10 6)
    ///     注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
    ///
    /// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
    ///
    /// 题目数据保证答案肯定是一个 32 位 的整数。
    ///
    /// 示例 1：
    ///
    ///     输入：s = "12"
    ///     输出：2
    ///     解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
    /// 示例 2：
    ///
    ///     输入：s = "226"
    ///     输出：3
    ///     解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
    /// 示例 3：
    ///
    ///     输入：s = "0"
    ///     输出：0
    ///     解释：没有字符映射到以 0 开头的数字。
    ///     含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
    ///     由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
    /// 示例 4：
    ///
    ///     输入：s = "06"
    ///     输出：0
    ///     解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
    ///
    /// 提示：
    ///
    ///     1 <= s.length <= 100
    ///     s 只包含数字，并且可能包含前导零。
    ///
    /// - 链接：https://leetcode-cn.com/problems/decode-ways
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：0 ms, 在所有 Swift 提交中击败了100.00%的用户
    ///     内存消耗：13.8 MB, 在所有 Swift 提交中击败了52.94%的用户
    ///     通过测试用例：269 / 269
    ///
    func numDecodings(_ s: String) -> Int {

        /* 2. DP
         11101
         - 0
         - 1
         1 (1) -> 1
         1 (1, 1), (11) -> 2
         1 (1, 11), (1, 1, 1), (11, 1) -> 3
         0 (1, 1, 10), (11, 10) -> 2
         1 (1, 1, 10, 1), (11, 10, 1) -> 2
         */
        
        var f0 = 0, f1 = 1, f2 = 0
        var start = s.startIndex
        var lastV = 0
        
        while start < s.endIndex {
            let v = s[start].wholeNumberValue!
            
            f2 = 0
            if lastV * 10 + v <= 26 {
                f2 = f0
            }

            if v == 0 {
                f0 = 0
                f1 = f2
                lastV = lastV * 10 + v
            } else {
                f2 += f1
                f0 = f1
                f1 = f2
                lastV = v
            }
            start = s.index(after: start)
        }
        
        // 1. DFS
        var paths: [[Int]] = []
        var path: [Int] = []
        func dfs(_ start: String.Index) {
            if start == s.endIndex {
                paths.append(path)
                return
            }
            
            let v = s[start].wholeNumberValue!
            
            if v == 0 {
                if let last = path.last, last > 0, last * 10 < 26 {
                    path[path.count - 1] = last * 10
                    dfs(s.index(after: start))
                } else {
                    return
                }
            } else {
                path.append(v)
                dfs(s.index(after: start))
                path.removeLast()
                
                if let last = path.last, last > 0, last * 10 + v < 26 {
                    path[path.count - 1] = last * 10 + v
                    dfs(s.index(after: start))
                }
            }
        }
        
        dfs(s.startIndex)
        
        return paths.count
    }
    
    // MARK: #139. 单词拆分
    
    /// #139. 单词拆分
    ///
    /// 给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
    ///
    /// 说明：拆分时可以重复使用字典中的单词。
    ///
    /// 示例 1：
    ///
    ///     输入: s = "leetcode", wordDict = ["leet", "code"]
    ///     输出: true
    ///     解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
    /// 示例 2：
    ///
    ///     输入: s = "applepenapple", wordDict = ["apple", "pen"]
    ///     输出: true
    ///     解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
    ///          注意你可以重复使用字典中的单词。
    /// 示例 3：
    ///
    ///     输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    ///     输出: false
    ///
    /// 提示：
    ///
    ///     1 <= s.length <= 300
    ///     1 <= wordDict.length <= 1000
    ///     1 <= wordDict[i].length <= 20
    ///     s 和 wordDict[i] 仅有小写英文字母组成
    ///     wordDict 中的所有字符串 互不相同
    ///
    /// - 链接：https://leetcode-cn.com/problems/word-break
    ///
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        
        let wordDict = wordDict.sorted().reversed()
        
#if false
        
        var flags = Array(repeating: -1, count: s.count)
        
        func dfs(_ start: String.Index) -> Bool {
            if start == s.endIndex {
                return true
            }
            
            let ss = s[start..<s.endIndex]
            
            for word in wordDict {
                if flags[s.distance(from: s.startIndex, to: start)] != -1 {
                    return dp[s.distance(from: s.startIndex, to: start)] == 1
                }
                if ss.count >= word.count, ss.hasPrefix(word), dfs(ss.index(start, offsetBy: word.count)) {
                    flags[s.distance(from: s.startIndex, to: start)] = 1
                    return true
                }
            }
            flags[s.distance(from: s.startIndex, to: start)] = 0
            return false
        }
        
        return dfs(s.startIndex)
        
#endif
        
        /*
         执行结果：通过
         
            执行用时：8 ms, 在所有 Swift 提交中击败了96.67%的用户
            内存消耗：13.7 MB, 在所有 Swift 提交中击败了95.00%的用户
            通过测试用例：45 / 45
         */
        let minLen = wordDict.reduce(20) { partialResult, ele in
            return min(ele.count, partialResult)
        }
        
        var dp = Array(repeating: 0, count: s.count)
        var idx = s.startIndex
        
        for i in 0..<s.count {
            
            if i < minLen - 1 {
                idx = s.index(after: idx)
                continue
            }
            
            for word in wordDict {
                let len = word.count
                if i - len + 1 < 0 { continue}
                
                let lowwer = s.index(idx, offsetBy: len-1)
                let upper = idx
                let ss = s[lowwer...upper]
                
                if (i-len < 0 || dp[i - len] == 1), word == ss {
                    dp[i] = 1
                    break
                }
            }
            
            idx = s.index(after: idx)
        }
        
        return dp.last! == 1
    }
}

// MARK: 第 16 天 - 动态规划 (-- 2021-11-25)
extension AlgorithmII {
    
    // MARK: ##300. 最长递增子序列
    
    /// #300. 最长递增子序列
    ///
    /// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
    ///
    /// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] /// 的子序列。
    ///
    /// 示例 1：
    ///
    ///     输入：nums = [10,9,2,5,3,7,101,18]
    ///     输出：4
    ///     解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    /// 示例 2：
    ///
    ///     输入：nums = [0,1,0,3,2,3]
    ///     输出：4
    /// 示例 3：
    ///
    ///     输入：nums = [7,7,7,7,7,7,7]
    ///     输出：1
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 2500
    ///     -10^4 <= nums[i] <= 10^4
    ///
    ///
    /// - 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
    /// 
    func lengthOfLIS(_ nums: [Int]) -> Int {
        
        var lisdp: [[Int]] = []
        var maxLen = 0
        
        for i in 0..<nums.count {
            var isInsert = false
            for j in (0..<lisdp.count).reversed() {
                var lis = lisdp[j]
                if lis.last! + 1 == nums[i] {
                    lisdp[j].append(nums[i])
                    maxLen = max(maxLen, lis.count + 1)
                    isInsert = true
                }
                else if lis.last! < nums[i] {
                    lis.append(nums[i])
                    lisdp.append(lis)
                    maxLen = max(maxLen, lis.count)
                    isInsert = true
                }
                else if lisdp[j].count == 1, lisdp[j].last! >= nums[i] {
                    lisdp.remove(at: j)
                    lisdp.insert([nums[i]], at: j)
                    isInsert = true
                }
            }

            if isInsert == false {
                lisdp.append([nums[i]])
                maxLen = max(maxLen, 1)
            }

            if lisdp.count < 2 {
                continue
            }

            for j in (0..<lisdp.count - 1).reversed() {
                let lis1 = lisdp[j]
                let lis2 = lisdp[j+1]

                if lis1.last! == lis2.last!, lis1.count != lis2.count {
                    lisdp.remove(at: lis1.count > lis2.count ? j+1 : j)
                }
                else if lis1.count == lis2.count, lis1.last! != lis2.last! {
                    lisdp.remove(at: lis1.last! > lis2.last! ? j : j+1)
                }
            }
        }
        
        // 2.
        var dp = Array(repeating: 1, count: nums.count)
        for i in 0..<nums.count {
            var maximum = 1
            for j in 0..<i {
                let jj = i - j - 1 // 倒序查询
                let distance = nums[i] - nums[jj]
                if distance > 0 {
                    maximum = max(maximum, dp[jj] + 1)
                    if maximum == i + 1 { break }
                }
                else if distance == 0 {
                    maximum = max(maximum, dp[jj])
                    break
                }
            }
            if maximum > 1 {
                dp[i] = maximum
            }
            maxLen = max(maxLen, maximum)
        }
        return lisdp.count
    }
    
    // MARK: #673. 最长递增子序列的个数
    
    /// #673. 最长递增子序列的个数
    ///
    /// 给定一个未排序的整数数组，找到最长递增子序列的个数。
    ///
    /// 示例 1:
    ///
    ///     输入: [1,3,5,4,7]
    ///     输出: 2
    ///     解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
    /// 示例 2:
    ///
    ///     输入: [2,2,2,2,2]
    ///     输出: 5
    ///     解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
    ///     注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
    ///
    /// - 链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：56 ms, 在所有 Swift 提交中击败了95.24%的用户
    ///     内存消耗：13.7 MB, 在所有 Swift 提交中击败了38.10%的用户
    ///     通过测试用例：223 / 223
    ///
    func findNumberOfLIS(_ nums: [Int]) -> Int {
        var dp = Array(repeating: 1, count: nums.count)
        var cnt = Array(repeating: 1, count: nums.count)
        var maxLen = 1
        
        for i in 0..<nums.count {
            var maximum = 1
            var c = 1
            for j in 0..<i {
                let jj = i - j - 1 // 倒序查询
                let distance = nums[i] - nums[jj]
                if distance > 0 {
                    if dp[jj] + 1 > maximum {
                        c = cnt[jj]
                    }
                    else if dp[jj] + 1 == maximum {
                        c += cnt[jj]
                    }
                    maximum = max(maximum, dp[jj] + 1)
                    if maximum == i + 1 { break }
                }
                else if distance == 0 {
                    
                    if dp[jj] > maximum {
                        c = cnt[jj]
                    }
                    else if dp[jj] == maximum {
                        c += cnt[jj]
                    }
                    
                    maximum = max(maximum, dp[jj])
                    break
                }
            }
            if maximum > 1 {
                dp[i] = maximum
                cnt[i] = c
            }
            maxLen = max(maxLen, maximum)
        }
        
        var count = 0
        for i in maxLen-1..<dp.count {
            if dp[i] == maxLen {
                count += cnt[i]
            }
        }
        return count
    }
}

// MARK: 第 17 天 - 动态规划 (-- 2021-11-26)
extension AlgorithmII {
    
    // MARK: #1143. 最长公共子序列
    
    /// #1143. 最长公共子序列
    ///
    /// 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
    ///
    /// 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何/// 字符）后组成的新字符串。
    ///
    ///     例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
    /// 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
    ///
    ///
    /// 示例 1：
    ///
    ///     输入：text1 = "abcde", text2 = "ace"
    ///     输出：3
    ///     解释：最长公共子序列是 "ace" ，它的长度为 3 。
    /// 示例 2：
    ///
    ///     输入：text1 = "abc", text2 = "abc"
    ///     输出：3
    ///     解释：最长公共子序列是 "abc" ，它的长度为 3 。
    /// 示例 3：
    ///
    ///     输入：text1 = "abc", text2 = "def"
    ///     输出：0
    ///     解释：两个字符串没有公共子序列，返回 0 。
    ///
    /// 提示：
    ///
    ///     1 <= text1.length, text2.length <= 1000
    ///     text1 和 text2 仅由小写英文字符组成。
    ///
    /// 链接：https://leetcode-cn.com/problems/longest-common-subsequence
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：44 ms, 在所有 Swift 提交中击败了61.70%的用户
    ///     内存消耗：13.5 MB, 在所有 Swift 提交中击败了98.94%的用户
    ///     通过测试用例：44 / 44
    ///
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        
//        var dp = Array(repeating: Array(repeating: 0, count: text2.count), count: text1.count)
        var flags = Array(repeating: 0, count: text2.count)
        
        var idx1 = text1.startIndex
        var idx2OffsetBy = 0 //
        var farFlagIdx = 0 // 记录最大长度值的远端下标。更新即跳出循环，减少遍历次数。
        
        for _ in 0..<text1.count {
            
            var lastFlag = 0
            if idx2OffsetBy > 0 { lastFlag = flags[idx2OffsetBy - 1] }
            var idx2 = text2.index(text2.startIndex, offsetBy: idx2OffsetBy)
            
            for j in idx2OffsetBy..<text2.count {
                
                if text1[idx1] == text2[idx2] {
//                    dp[i][j] = 1
//                    dp[i][j] = dp[i - 1][j - 1] + 1
//                    dp[i][j] = lastFlag + 1
                    
                    let temp = flags[j]
                    flags[j] = lastFlag + 1
                    lastFlag = max(lastFlag, temp)
                    
                    if flags[j] == j + 1 {
                        idx2OffsetBy += 1
                    }
                    
                    if flags[farFlagIdx] < flags[j] {
                        farFlagIdx = j
                        break
                    }
                    
                } else {
//                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
                    lastFlag = max(lastFlag, flags[j])
                }
                
                idx2 = text2.index(after: idx2)
            }
            
            idx1 = text1.index(after: idx1)
        }
        
        return flags.max()!
    }
    
    // MARK: #583. 两个字符串的删除操作
    
    /// #583. 两个字符串的删除操作
    ///
    /// 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
    ///
    /// 示例：
    ///
    ///     输入: "sea", "eat"
    ///     输出: 2
    ///     解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
    ///
    /// 提示：
    ///
    ///     给定单词的长度不超过500。
    ///     给定单词中的字符只含有小写字母。
    ///
    /// 链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings
    ///
    /// 执行结果：通过
    ///
    ///     执行用时：28 ms, 在所有 Swift 提交中击败了90.91%的用户
    ///     内存消耗：13.9 MB, 在所有 Swift 提交中击败了100.00%的用户
    ///     通过测试用例：1306 / 1306
    ///
    func minDistance(_ text1: String, _ text2: String) -> Int {

        var flags = Array(repeating: 0, count: text2.count)
        
        var idx1 = text1.startIndex
        var idx2OffsetBy = 0
        var farFlagIdx = 0 // 更新最大长度值的远端下标
        
        for _ in 0..<text1.count {
            
            var lastFlag = 0
            if idx2OffsetBy > 0 { lastFlag = flags[idx2OffsetBy - 1] }
            var idx2 = text2.index(text2.startIndex, offsetBy: idx2OffsetBy)
            
            for j in idx2OffsetBy..<text2.count {
                
                if text1[idx1] == text2[idx2] {

                    let temp = flags[j]
                    flags[j] = lastFlag + 1
                    lastFlag = max(lastFlag, temp)
                    
                    if flags[j] == j + 1 {
                        idx2OffsetBy += 1
                    }
                    
                    if flags[farFlagIdx] < flags[j] {
                        farFlagIdx = j
                        break
                    }
                    
                } else {
                    lastFlag = max(lastFlag, flags[j])
                }
                
                idx2 = text2.index(after: idx2)
            }
            
            idx1 = text1.index(after: idx1)
        }
        
        return text1.count + text2.count - 2 * flags.max()!
    }
}

// MARK: 第 18 天 - 动态规划 (-- 2021-12-01)
extension AlgorithmII {
    
    // MARK: #72. 编辑距离
    
    // MARK: #322. 零钱兑换
    
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        let sortedCoins = coins.sorted()
                
        var remaind = amount
        var cnt = 0
        
        while remaind > 0 {
            let idx = BinarySearch.findLast(sortedCoins, lessThanOrEqualTo:remaind)
            if idx == -1 {
                break
            }
            cnt += 1
            remaind -= coins[idx]
        }
        return cnt
    }
    
    func coinChange2(_ coins: [Int], _ amount: Int) -> Int {
        if amount == 0 { return 0 }
        let sortedCoins = coins.sorted().reversed() as [Int]
        
        var sums = Array(repeating: 0, count: amount)
        
        func count(_ indexset: [Int]) -> Int {
            var value = 0
            for idx in 0..<indexset.count {
                value += indexset[idx]
            }
            return value
        }
        
        func coinsum(_ indexset: [Int]) -> Int {
            var value = 0
            for idx in 0..<indexset.count {
                value += sortedCoins[idx] * indexset[idx]
            }
            return value
        }
        
        func bfs(_ indexsets: [[Int]]) -> Int {
            var news: [[Int]] = []
            for indexset in indexsets {
                let v = coinsum(indexset)
                for i in 0..<sortedCoins.count {
                    let v1 = v + sortedCoins[i]
                    if v1 > amount {
                        continue
                    }
                    if v1 == amount {
                        return count(indexset) + 1
                    } else if sums[v1] > 0 {
                        continue
                    }
                    var idxset = indexset
                    idxset[i] += 1
                    news.append(idxset)

                    sums[v1] = count(idxset)
                }
            }
            
            if news.count == 0 { return -1 }
            return bfs(news)
        }
        
        let indexset = Array(repeating: 0, count: sortedCoins.count)
        return bfs([indexset])
    }
    
    
    // MARK: #343. 整数拆分
    
    /// 343. 整数拆分
    ///
    /// 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
    ///
    /// 示例 1:
    ///
    ///     输入: 2
    ///     输出: 1
    ///     解释: 2 = 1 + 1, 1 × 1 = 1。
    /// 示例 2:
    ///
    ///     输入: 10
    ///     输出: 36
    ///     解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    /// 说明: 你可以假设 n 不小于 2 且不大于 58。
    ///
    /// 链接：https://leetcode-cn.com/problems/integer-break
    func integerBreak(_ n: Int) -> Int {
//        if n < 2 { return 0 }
//        if n == 2 { return 1 }
//        if n == 3 { return 2 }
//        if n == 4 { return 4 }
//        if n == 5 { return 6 }
//        if n == 6 { return 9 }
//
//        var dp = [4,6,9]
//        for _ in 7...n {
//            let mul = max(dp[0] * 3, dp[1] * 2, dp[2] * 1)
//            dp.removeFirst()
//            dp.append(mul)
//            print(mul)
//        }
        
        if n == 2 { return 1 }
        if n == 3 { return 2 }

        var dp = [0,1,2]
        for v in 4...n {
            let mul = max(max(v - 3, dp[0]) * 3, max(v - 2, dp[1]) * 2)
            dp.removeFirst()
            dp.append(mul)
            print(mul)
        }
        
        return dp.last!
    }
}

// MARK: 第 19 天 - 位运算 (-- 2021-11-29)
extension AlgorithmII {
    
    // MARK: #201. 数字范围按位与
    
    /// #201. 数字范围按位与
    ///
    /// 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
    ///
    /// 示例 1：
    ///
    ///     输入：left = 5, right = 7
    ///     输出：4
    /// 示例 2：
    ///
    ///     输入：left = 0, right = 0
    ///     输出：0
    /// 示例 3：
    ///
    ///     输入：left = 1, right = 2147483647
    ///     输出：0
    ///
    /// 提示：
    ///
    ///     0 <= left <= right <= 231 - 1
    ///
    /// 链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range
    ///
    func rangeBitwiseAnd(_ left: Int, _ right: Int) -> Int {
        
        /*
         执行用时：2164 ms, 在所有 Swift 提交中击败了20.00%的用户
         内存消耗：13.6 MB, 在所有 Swift 提交中击败了80.00%的用户
         通过测试用例：8268 / 8268
         */
//        var value = 0xffffffff
//        for v in left...right {
//            value &= v
//        }
//        return value
        
        /* 2012-12-03
         
         left = 5  = 0x101
         right = 7 = 0x111
         res = 0x100 = 4
         
         left = 16  = 0x1 0000
         right = 15 = 0x0 1111
         res = 0x 0x0 0000
         分析：从高位到低位，第一个不同的数位及后面部分丢弃。
         
         执行用时：28 ms, 在所有 Swift 提交中击败了100.00%的用户
         内存消耗：13.6 MB, 在所有 Swift 提交中击败了100.00%的用户
         通过测试用例：8268 / 8268
         */
        var res = 1 << 31
        var idx = 31
        for _ in 0..<31 {
            if res & left == res & right {
                res = res >> 1
                idx -= 1
            } else {
                break
            }
        }
        return ( (left >> idx) << idx )
    }
    
}

// MARK: 第 20 天 - 其他 (-- 2021-12-02)
extension AlgorithmII {
    
    // MARK: #384. 打乱数组
    
    /// #384. 打乱数组
    ///
    /// 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
    
    /// 实现 Solution class:
    ///
    ///     Solution(int[] nums) 使用整数数组 nums 初始化对象
    ///     int[] reset() 重设数组到它的初始状态并返回
    ///     int[] shuffle() 返回数组随机打乱后的结果
    ///

    /// 示例：
    ///
    ///     输入
    ///     ["Solution", "shuffle", "reset", "shuffle"]
    ///     [[[1, 2, 3]], [], [], []]
    ///     输出
    ///     [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
    ///     解释
    ///     Solution solution = new Solution([1, 2, 3]);
    ///     solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
    ///     solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
    ///     solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
    ///
    /// 提示：
    ///
    ///     1 <= nums.length <= 200
    ///     -106 <= nums[i] <= 106
    ///     nums 中的所有元素都是 唯一的
    ///     最多可以调用 5 * 104 次 reset 和 shuffle
    ///
    /// 链接：https://leetcode-cn.com/problems/shuffle-an-array
    static var k384Nums = "k384Nums"
    private var nums: [Int] {
        set {
            objc_setAssociatedObject(self, &Self.k384Nums, newValue, .OBJC_ASSOCIATION_ASSIGN)
        }
        get {
            return objc_getAssociatedObject(self, &Self.k384Nums) as! [Int]
        }
    }

    convenience init(_ nums: [Int]) {
        self.init()
        self.nums = nums
    }
    
    func reset() -> [Int] {
        return self.nums
    }
    
    func shuffle() -> [Int] {
        var nums = Array(self.nums)
        
        for i in 0..<nums.count {
            let random = Int.random(in: i..<nums.count)
            if i == random { continue }
            let temp = nums[i]
            nums[i] = nums[random]
            nums[random] = temp
        }

        return nums
    }
    
    // MARK: #202. 快乐数
    
    /// #202. 快乐数
    /// 编写一个算法来判断一个数 n 是不是快乐数。
    ///
    /// 「快乐数」定义为：
    ///
    ///     对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
    ///     然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
    ///     如果 可以变为  1，那么这个数就是快乐数。
    /// 如果 n 是快乐数就返回 true ；不是，则返回 false 。
    ///
    /// 示例 1：
    ///
    ///     输入：n = 19
    ///     输出：true
    ///     解释：
    ///     12 + 92 = 82
    ///     82 + 22 = 68
    ///     62 + 82 = 100
    ///     12 + 02 + 02 = 1
    /// 示例 2：
    ///
    ///     输入：n = 2
    ///     输出：false
    ///
    /// 提示：
    ///
    ///     1 <= n <= 231 - 1
    ///
    /// 链接：https://leetcode-cn.com/problems/happy-number
    
    func isHappy(_ n: Int) -> Bool {
        var dp = Array(repeating: 0, count: 500)
        
        func _nextNumber(_ value: Int) -> Int {
            let dividend = 10
            var next = 0
            
            var quotient = value
            var remainder = 0
            while quotient > 0 {
                remainder = quotient % dividend
                quotient = quotient / dividend
                next += remainder * remainder
            }

            return next
        }
        
//        func _isHappy(_ value: Int) -> Bool {
//            let sum = _nextNumber(value)
//            if sum == 1 {
//                return true
//            }
//            if sum < dp.count {
//                if dp[sum] == 1 { return false}
//                dp[sum] = 1
//            }
//            return _isHappy(sum)
//        }
//        return _isHappy(n)
        
        var sum = n
        while sum > 1 {
            if sum < dp.count {
                if dp[sum] == 1 { return false }
                dp[sum] = 1
            }
            sum = _nextNumber(sum)
        }
        
        /* 在数学上，非快乐数最后都会进入循环链 (num -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4)
         */
        return true
    }

    /// 位数分离。一个正整数，分离为它每个位数上的数字集合[a0, a1, ..., an]。
    func digitSplit(_ dividor: Int, dividend: Int = 10) -> [Int] {
        if dividor == 0 { return [0] }
        
        var quotient = dividor
        var remainder = 0
        var nums: [Int] = []

        while quotient > 0 {
            remainder = quotient % dividend
            quotient = quotient / dividend
            nums.append(remainder)
        }
        
        return nums
    }
    
    // MARK: #149. 直线上最多的点数
    func maxPoints(_ points: [[Int]]) -> Int {
        if points.count == 1 { return 0 }

        var lines: [[Int]] = []
        var cnts: [Int] = []

        for i in 1..<points.count {

            for j in 0..<i {
                let p1 = points[i], p2 = points[j]
                let ABC = LineEquation.getABC(p1, p2)
                if lines.contains(ABC) {
                    let idx = lines.firstIndex(of: ABC)
                    cnts[idx!] += 2
                } else {
                    lines.append(ABC)
                    cnts.append(2)
                }
            }
        }
        
        return Int(sqrt(Double(cnts.max() ?? 0))) + 1
    }
}
